Bubble sort array

[hüli86]

Hallo kann man hier den sortier algorithmus
ohne dem bubble sort machen




import java.io.*;

class Aufgabe2{
public static void main(String [] args) throws IOException{

//Variablen deklarieren und initialisieren
int n = 0, i, j, tauschop=0, verg=0, flag=0;
double tmp=0;

BufferedReader eingabe = new BufferedReader(new InputStreamReader(System.in));

System.out.print("Geben Sie bitte eine Zahl n groesser 6 ein: ");
n = Integer.parseInt(eingabe.readLine());

//Solange eingegebene Zahl kleiner 6, Eingabe wiederholen
while( n <= 6 ){
System.out.print("Die Zahl muss groesser 6 sein. Bitte noch mal eingeben: ");
n= Integer.parseInt(eingabe.readLine());
}

//Ein Array vom Typ double mit n Elementen erzeugen
double [] array2sort = new double[n];

//Die Array-Felder mit Zahlen füllen
for (i=0; i < n; i++){
System.out.print("Ihre "+(i+1)+". Zahl bitte: ");
array2sort = Double.parseDouble(eingabe.readLine());
}

//Ausgabe des Arrays vor der Sortierung
System.out.println("Der Array vor der Sortierung: ");

for (i=0; i < array2sort.length; i++){
System.out.print(array2sort+" ");
}

//Sortier-Algorithmus

for (i = 0; i < array2sort.length-1; i++){
flag = 0;
for (j = array2sort.length-1; j > i; j--){
verg++;
if (array2sort[j] < array2sort[j-1]){
tmp = array2sort[j];
array2sort[j] = array2sort[j-1];
array2sort[j-1] = tmp;
tauschop++;
flag = 1;
}
}
if (flag == 0)
break;
}

//Ausgabe Anzahl der Tauschoperationen und der Vergleiche
System.out.println("\nAnzahl der Tauschoperationen: "+tauschop+"\tAnzahl der Vergleiche: "+verg);

//Ausgabe des Arrays nach der Sortierung
System.out.println("\nDer Array nach der Sortierung: ");

for (i=0; i < array2sort.length; i++){
System.out.print(array2sort+" ");
}

}

}

 

[EOB]

was ist los?

1. code tags nutzen

2. frage so formulieren, dass man sie versteht



gruesse

 

[Guest]

Ja

 

[The_S]

lol, omfg ... :roll:

Man kann nicht wirklich verstehen, was du für ein Problem hast. Versuch es nochmal anders zu erklären

 

[Leroy42]

Ich codetagge mal:

import java.io.*;

class Aufgabe2{
  public static void main(String [] args) throws IOException{
    
    //Variablen deklarieren und initialisieren
    int n = 0, i, j, tauschop=0, verg=0, flag=0;
    double tmp=0;
    
    BufferedReader eingabe = new BufferedReader(new InputStreamReader(System.in));
    
    System.out.print("Geben Sie bitte eine Zahl n groesser 6 ein: ");
    n = Integer.parseInt(eingabe.readLine());
    
    //Solange eingegebene Zahl kleiner 6, Eingabe wiederholen
    while( n  <= 6 ){
      System.out.print("Die Zahl muss groesser 6 sein. Bitte noch mal eingeben: ");
      n= Integer.parseInt(eingabe.readLine());
    }
    
    //Ein Array vom Typ double mit n Elementen erzeugen
    double [] array2sort = new double[n];
    
    //Die Array-Felder mit Zahlen füllen
    for (i=0; i < n; i++){
      System.out.print("Ihre "+(i+1)+". Zahl bitte: ");
      array2sort[i] = Double.parseDouble(eingabe.readLine());
    }
    
    //Ausgabe des Arrays vor der Sortierung
    System.out.println("Der Array vor der Sortierung: ");
    
    for (i=0; i < array2sort.length; i++){
      System.out.print(array2sort[i]+" ");
    }
    
    //Sortier-Algorithmus
    
    for (i = 0; i < array2sort.length-1; i++){
      flag = 0;
      for (j = array2sort.length-1; j > i; j--){
        verg++;
        if (array2sort[j]  < array2sort[j-1]){
          tmp = array2sort[j];
          array2sort[j] = array2sort[j-1];
          array2sort[j-1] = tmp;
          tauschop++;
          flag = 1;
        }
      }
      if (flag == 0)
        break;
    }
    
    //Ausgabe Anzahl der Tauschoperationen und der Vergleiche
    System.out.println("\nAnzahl der Tauschoperationen: "+tauschop+"\tAnzahl der Vergleiche: "+verg);
    
    //Ausgabe des Arrays nach der Sortierung
    System.out.println("\nDer Array nach der Sortierung: ");
    
    for (i=0; i < array2sort.length; i++){
      System.out.print(array2sort[i]+" ");
    }
    
  }

 

[Leroy42]

Hallo kann man hier den sortier algorithmus
ohne dem bubble sort machen

Ja, du kannst einen anderen Sortieralgorithmus implementieren
(davon gibts Dutzende) oder du ninmmst Java's eingebauten.

Beim letzteren hast du allerdings keine Möglichkeiten, dir die
Anzahl der benötigten Vertauschungen auszugeben.

 

[EOB]

es gibt zum beispiel den quicksort. oder du schaust mal hier nach: sortieralgorithmen

ich liebe diese laufzeitbestimmungen :roll: ... wer kann denn hier gliech mal verstaendlich komplexitaet und obere /untere schranken erklaeren?

gruesse :lol: :lol:

 

[Leroy42]

wer kann denn hier gliech mal verstaendlich komplexitaet und obere /untere schranken erklaeren?

Falls die Frage ernstgemeint war:

Ein Algorithmus hat die Komplexität O(f(n)), wenn, bis auf Konstanten, gilt,
daß die Laufzeit (Speicherverbrauch, ...) proportional zu f(n) für n Eingabewerte ist.

BubbleSort : O(n²)
QuickSort : O(n * log n)

Besser schaust du hier: wiki Komplexität

 

[EOB]

so das es jeder versteht....was bedeutet denn eine komplexitaet von O(f(n)) oder O(f(g(n))) und so weiter....das meinte ich ;-). ich habs durch...zum glueck. wollts nicht unbedingt erklaert haben.

gruesse

 

[Marco13]

"so das es jeder versteht" ist eine sehr starke Anforderung.
"richtig" ist auch eine starke Anforderung.
Bisher wurde keine von beiden erfüllt.

Richtig:

<=>

Vielleicht verständlich:
Die Zeit, die ein Sortierverfahren zum Sortieren benötigt, hängt davon ab, wieviele Elemente sortiert werden müssen. Die Zeit, die ein Algorithmus im schlechtesten Fall (worst case) für das Sortieren benötigt, schätzt man nach oben mit der O-Notation ab. Wenn man die Zeit, die im schlechteste Fall benötigt wird, um n Elemente zu sortieren, mit f(n) bezeichnet, dann bedeutet

, dass diese Zeit asymptotisch bei steigender Eingabegröße "höchstens so schnell wächst, wie g". Wenn die Eingabegröße eine bestimmte Grenze überschreitet, wird von dort an immer weniger Zeit benötigt, als durch c*g(n) angegeben ist (für c>0).

 

[Leroy42]

Richtig:

<=>

<HalbIronisch>Ach, wie ich das vermisse</HalbIronisch>

Die Zeit, die ein Algorithmus im schlechtesten Fall (worst case) für das Sortieren benötigt, schätzt man nach oben mit der O-Notation ab. Wenn man die Zeit, die im schlechteste Fall benötigt wird, um n Elemente zu sortieren, mit f(n) bezeichnet, dann b

:shock: Ist das wirklich so? Im schlechtesten Fall?

Dem würde doch widersprechen, daß Quicksort ein Laufzeitkomplexität
von O(n*log n) zugesprochen wird. Im schlimmsten Fall (dann wenn jedes
gewählte Pivot-Element den Array nur um ein Index verkleinert), ist die Laufzeit
aber doch wesentlich größer. ???:L

 

[Marco13]

Nun, man kann auch die Zeit, die im besten Fall benötigt wird, mit der O-Notation abschätzen - nur macht das meistens nicht viel Sinn. Gelegentlich wird auch der Average-Case abgeschätzt. Aber "üblich" (und imho am sinnvollsten) ist die Worst-Case Zeit. Und die ist bei QuickSort tatsächlich O(n^2). Deswegen wird z.B. bei Arrays.sort (meistens) MergeSort verwendet, was auch im worst case O(nlog(n)) hat.

 

[Lim_Dul]

Quicksort ist ein Vertreter, der etwas aus der Reihe tanzt.

Quicksort liegt tatsächlich nur in O(n^2) und nicht in O(n log n).

Allerdings wird meistens der randomisierte Quicksort eingesetzt und bei randomisiertieren Algorithmen interessiert man sich dann für die erwartete Laufzeit. Und diese liegt bei dem randomisierten Quicksort in Theta(n log n), also auch in O(n log n).

MergeSort hat gegenüber Quicksort einen großen Nachteil, dass MergeSort deutlich mehr temporären Speicher als Quicksort braucht.