Bubble Sort Trockentest

2 Antworten

Nimm Dir ein paar Zahlen, schreib sie durcheinander auf und gehe Dein Programm Zahl für Zahl durch. Nach jedem Durchlauf bekommst Du ne neue Reihenfolge der Zahlen (auch mit aufschreiben) und wenn alles richtig ist, sind die Zahlen am Ende sortiert. Also alles mit Stift und Zettel und Deinem Programmentwurf.

Nimm einfach ein Paar Zahlen, misch sie und lass es sortieren.

Welcher Sortieralgorithmus ist unter welchen Umständen der schnellste?

Nabend.

Da ich mich ja mit der Programmierung beschäftige, habe ich versucht, einige Sortieralgorithmen in C++ nachzuprogrammieren (und mir danach die schnelleren Versionen aus dem Netz raus zu suchen). Dann wollte ich anhand einer Liste von 500.000 Elementen testen, welcher Algorithmus der Schnellste ist.

Getestet habe ich bisher std::sort, Quick Sort, Insertion Sort und Timsort. std::sort war bei der unsortierten Liste zwei Millisekunden schneller als Timsort, danach folgte Insertion Sort und Quick Sort war letzter. Wenn ich aber ein neues Element zu der sortierten Liste hinzugefügt habe, war Timsort der schnellste Algorithmus mit sage und schreibe 0 Mikrosekunden. Danach folgten Insertion Sort, std::sort und zu guter letzt war mal wieder Quick Sort fertig.

Wenn ich das ganze kurz zusammenfassen sollte, würde ich sagen, dass Timsort an dieser Stelle der beste Sortieralgorithmus ist, auch wenn er zwei Millisekunden langsamer bei der Sortierung einer komplett unsortierten Liste als std::sort ist. Zwei Millisekunden sind vernachlässigbar, vor allem, wenn std::sort bei der Sortierung der bereits sortierten Liste mit einem neuen Element 9 Millisekunden braucht, während Timsort nicht mal eine Mikrosekunde benötigt.

Gibt es Sortieralgorithmen, die noch schneller sind als die vier vorhin genannten? Oder welche anderen Szenarien könnte ich testen?

Gruß

...zur Frage

Kann mir jemand diesen Java-Code für das Bubble Sort Verfahren erklären?

Hi, kann mir jemand diesen Java Code für das Bubble Sort Verfahren in Bezug auf folgende Fragen erklären?

public class BubbleSort { 
public static void sortiere(int[] x) {
  boolean unsortiert=true;
  int temp;
  
  while (unsortiert){
     unsortiert = false;
     for (int i=0; i < x.length-1; i++) 
        if (x[i] > x[i+1]) {                      
           temp       = x[i];
           x[i]       = x[i+1];
           x[i+1]     = temp;
           unsortiert = true;
        }          
  } 
}

public static void main(String[] args) {
  int[] liste = {0,9,4,6,2,8,5,1,7,3};
  sortiere(liste);
  for (int i=0; i<liste.length; i++) 
     System.out.print(liste[i]+" ");    
   } 
}

Der Code entstammt von dieser Seite: http://www.java-uni.de/index.php?Seite=85 Dort wird er aber nicht erklärt.. - Was bedeutet der Befehl "boolean"? - Was meint man mit int temp? - Wie läuft die while-Schleife ab, wenn innerhalb davon eine for-Schleife und innerhalb davon verschiedene if-Bedingungen aufgelistet sind?

Ich hoffe jemand nimmt sich die Zeit. Wär Euch sehr dankbar. :)

...zur Frage

Was möchtest Du wissen?