Google-Anzeigen

Sortieralgorithmen gibt es offenbar wie Sand am Meer. Wenn ich ExcelSort nicht mitzähle (da es sich hierbei um keinen Algorithmus handelt) habe ich nun 20 verschiedene Methoden in VBA programmiert und erläutert(siehe neben diesem Thread hier Monolog über Sortieralgorithmen und Monolog über Sortieralgorithmen (2. Teil)). Dies sind die Methoden BubbleSort, BiDiBubbleSort, OetSort, PositionSort, AllocationSort, SwirlSort, MinSort, MinMaxSort, RlxSort, MinsertionSort, GnomeSort, InsertionSort, NoNetSort, CombSort, ShellSort, HeapSort, BucketSort, MergeSort, SplitSort und QuickSort. Schaut man sich im Web um, tauchen jedoch immer weitere auf, z.B. Intersort (auf ActiveVB - Sortieralgorithmen) Avlsort, Bsort, Bitonicsort, Bitonic Mergesort, Countingsort, Jumpsort, MSsort, Partitsort, Plaselsort, Radixsort, Ripplesort, Selectsort, Shakersort, Shearsort, Simplesort, Tepifsort, Trippelsort (auf Allgemeine und spezielle Sortieralgorithmen) Binary Tree Sort, Bogosort, Introsort, Selectionsort, Cocktailsort, Slowsort, Smoothsort, Stoogesort, Swap-Sort (auf Sortierverfahren – Wikipedia) Viele von denen sind den hier vorgestellten oftmals sehr ähnlich, manche sind einfach zu aufwendig wieder andere hab ich gar nicht kapiert. Freilich reizt das zur weiteren Vertiefung, aber einmal muss Schluss sein. ;-) Umfangreiche Erläuterungen zu Komplexität und Speicherbedarf, Best Case, Average Case und Worst Case spare ich mir, das ist mir einfach zu aufwendig. Wen das tiefergreifend interessiert, der schaue doch bitte u.a. bei Sortierverfahren – Wikipedia vorbei. Ich gebe hier lediglich einen Vergleich der wichtigsten Eigenschaften und der von mir gemessenen Zeiten aller Verfahren bei jeweils gleichen Datenmengen. Einige Varianten wurden nicht geprüft, da sie einfach zu zeitaufwendig wären. Alle Algorithmen hatten exakt die gleichen Daten in der gleichen Reihenfolge zu sortieren. Es handelte sich dabei ausschließlich um natürliche Zahlen zwischen 1 und 1.000.000.   A B C D E F G H I J 1 Eigenschaften und Zeitaufwand der Sortiermethoden in Sekunden 2 Methode Eigenschaften Durchläufe (Anzahl der Elemente) 3   in-place stabil rekursiv 655 1000 6553 10000 65536 131072 4 ExcelSort - - - 0,0469 0,0469 0,063 0,078 0,28 geht nicht 5 BucketSort (*) nein ja nein 0,1406 0,1406 0,155 0,155 0,19 0,23 6 QuickSort ja nein ja 0,0000 0,0000 0,016 0,031 0,25 0,58 7 HeapSort ja nein nein 0,0000 0,0000 0,031 0,063 0,50 1,08 8 CombSort ja nein nein 0,0000 0,0000 0,047 0,063 0,59 1,16 9 MergeSort nein ja ja 0,0000 0,0000 0,047 0,078 0,63 1,33 10 ShellSort ja nein nein 0,0000 0,0000 0,031 0,063 0,63 1,55 11 SplitSort nein ja ja 0,0000 0,0146 0,078 0,142 1,00 2,14 12 InsertionSort ja ja nein 0,0156 0,0469 2,281 5,313 235,08 nicht getestet 13 MinMaxSort ja nein nein 0,0166 0,0469 2,406 5,577 240,20 nicht getestet 14 MinSort ja nein nein 0,0313 0,0625 2,797 6,531 283,09 nicht getestet 15 MinsertionSort ja nein nein 0,0469 0,1094 4,047 9,469 409,81 nicht getestet 16 NoNetSort ja ja nein 0,0469 0,0938 4,422 10,328 448,30 nicht getestet 17 BiDiBubbleSort ja ja nein 0,0469 0,1104 4,890 11,515 505,63 nicht getestet 18 OetSort ja ja nein 0,0615 0,1250 5,235 12,203 530,23 nicht getestet 19 BubbleSort ja ja nein 0,0469 0,1250 5,266 12,313 537,30 nicht getestet 20 PositionSort nein ja nein 0,0625 0,1563 6,344 14,813 644,23 nicht getestet 21 RlxSort nein ja nein 0,0625 0,1563 6,516 15,188 664,56 nicht getestet 22 GnomeSort ja ja nein 0,0781 0,1865 8,047 18,797 815,00 nicht getestet 23 AllocationSort nein ja nein 0,0938 0,2344 10,375 24,172 1058,02 nicht getestet 24 SwirlSort nein nein nein 2,7500 7,1729 n. getestet n. getestet n. getestet nicht getestet 25 (*) = außer Konkurrenz, da nur bedingt verwendbar Excel Tabellen im Web darstellen >> Excel Jeanie HTML 4 Erläuterung der Eigenschaften: in-place: Die Daten müssen nicht temporär dupliziert werden, Vertauschungen finden direkt im Original-Array statt stabil: Elemente gleichen Inhalts bleiben in der ursprünglichen Reihenfolge rekursiv: Code wird aus sich selbst heraus mehrmals aufgerufen und befindet sich daher u.U. mehrfach im Speicher Es bleibt dabei: QuickSort ist der schnellste Algorithmus überhaupt. Er arbeitet sogar in-place aber leider auch rekursiv und instabil. MergeSort ist das schnellste stabile Verfahren, es arbeitet aber leider nicht in-place und ist ebenfalls rekursiv. HeapSort ist das schnellste rein iterative (also nicht rekursive) Verfahren. Dieses arbeitet jedoch leider nicht stabil. InsertionSort ist das schnellste stabile Verfahren, welches gleichzeitig nicht rekursiv ist und in-place arbeitet (welches also weder den Code noch die Daten duplizieren muss). Es gehört jedoch nicht zu den wirklich schnellen Verfahren (was man bei den Datenmengen über 10000 Elementen deutlich erkennen kann. Die eierlegende Wollmilchsau unter den Sortieralgorithmen ist also noch nicht gefunden. Dies wäre ein Verfahren, welches die Merkmale - stabil - in-place - nicht rekursiv hat und trotzdem an die Geschwindigkeit von QuickSort und MergeSort heranreicht. Es bleibt also durchaus noch was zu tun!

Google-Anzeigen