Sortierverfahren

[Landreas]

Hi,

unser Prof. hat uns die Aufgabe gegeben ein Array, welches einmal unsortiert, einmal aufsteigend und einmal absteigend sortiert ist, mittels den langsamen Sortierverfahren InsertionSort, SelectionSort, BubbleSort (mit und ohne Merker) und den schnellen Sortierverfahren QuickSort, MergeSort, HeapSort und ShellSort zu sortieren. Das läuft auch alles wunderbar, und auf einem Rechner mit Pentium 4 3 GHz und 1 GB Ram kommen bei einem Array mit 25.000 Werten folgende Ergebnisse raus: (Dauer in Millisekunden)

Verfahren random / asc* / desc**

InsertionSort: 875 / 0/ 1609
SelectionSort: 1344 / 906 / 891
BubbleS. o. M.: 3219 / 1000 / 2015
BubbleS. m. M.: 3235 / 0 / 2156

QuickSort: 0 / 0 / 0
MergeSort: 0 / 16 / 0
HeapSort: 16 / 0 / 15
ShellSort: 16 / 0 / 0

* Array ist bereits aufsteigend sortiert
** Array ist absteigend sortiert

Nun wollte ich von jemandem wissen, der sich etwas mit den Verfahren auskennt, ob diese krassen Zeitunterschiede zwischen den langsamen und schnellen wirklich stimmen können, kann mir das irgendwie kaum vorstellen.

 

[Gast]

Die Messungen stimmen wahrscheinlich.

Bei unsortierten Mengen ist Quicksort immer die erste Wahl.
Bei teilweise vorsortierten Mengen ist Quicksort allerdings sehr schlecht und Bubblesort und Insertionsort schneiden viel besser ab. Aber große Mengen mit vorsortiertem Inhalt (ca. 1000) sind für Heapsort/Shellsort wieder besser.

 

[mic_checker]

Also was Quicksort betrifft stimme ich dir nicht ganz zu. Quicksort hat keine gesicherte Laufzeit wie z.B. Mergesort, im worst case liegt die komplexität von Quicksort bei O(n²)....

Ab einer best. Datenmenge ist Heapsort afaik auch schneller als (Clever)QuickSort.

 

[Landreas]

Ok ich habe es mal mit dem bereits von Java zur Verfügung gestellten QuickSort in der sort-Methode der Arrays-Klasse überprüft und die Geschwindigkeit scheint wirklich zu stimmen. Unglaublich, wie groß der Unterschied zwischen diesen Verfahren ist

 

[mic_checker]

Es ist eigentlich recht logisch...du müsstest das ganze noch mit mehr Datensätzen probieren (also mehr als 25.000).

Zum Vergleich:
BubbleSort liegt in der Komplexitätsklasse O(n²) , Merge Sort in O(n * log n).

Es kommt ja auch nicht nur auf die Ausführungsgeschwindigkeit an, du musst ja auch schauen das best. Algorithmen für best. Datenstrukturen besser geeignet sind als andere. Ein weiterer Faktor bei der Wahl eines Sortieralgos ist ja dann noch ob du gesicherte Laufzeiten haben willst etc. pp.....

 

[kopfsalat]

...und wenn man z.B. nur Integer-Zahlen in einem bestimmten, nicht zu großen, Bereich sortieren will, bietet sich auch sowas wie CountingSort / BucketSort / RadixSort an, der ist dann nochmals schneller als O(n*log(n)), nämlich O(n).

Z.B. Sortiere 70000 Zahlen im Bereich von 0-500:
- Erzeuge Array B von 0-500
- Gehe das Ausgangsarray komplett durch und zähle in dem Array B an der Stelle des Wertes einen rauf
- Gehe das Array B der Reihe nach durch und überschreibe sooft wie vorhanden im Ausgangsarray die Zahlen in der gewünschten Reihenfolge.

 

[mic_checker]

Siehe auch Wikipedia. Von da ausgehend kann man sich weitere Informationen zu den oben genannten Verfahren wie QuickSort, MergeSort, RadixSort etc. holen.