\nWelcher Algorithmus ist hier der beste?<\/strong> Gegeben sei eine unsortierte Liste von Zahlen (die Zahl steht f\u00fcr die entg\u00fcltige Senderplatzierung) sowie eine Vergleichsfunktion und eine Funktion zum Vertauschen von zwei Kanalpl\u00e4tzen. Gesucht ist der g\u00fcnstigste Algorithmus, um die Zahlen zu sortieren. G\u00fcnstig meint minimal bzgl. der Summe der Distanzen, \u00fcber die Kan\u00e4le vertauscht werden. Die Distanzen sind deshalb wichtig, weil ich auf der Fernbedienung entsprechend oft „vor“ bzw. „zur\u00fcck“ dr\u00fccken muss. Dies sollte minimal sein.<\/p>\n
Die erste Idee ist nat\u00fcrlich, die klassischen Suchalgorithmen zu untersuchen. Ich bin nach Selection Sort<\/a> vorgegangen. Quicksort<\/a> f\u00e4llt mir ein, weil dort auch Elemente vertauscht werden. Auch Bubble Sort<\/a> nicht vergessen, weil dort nur benachbarte Elemente vertauscht werden, die Distanz also immer 1 ist. <\/p>\n Vielleicht gibt es einen anderen g\u00fcnstigen Algorithmus, weil wir hier ja Besonderheiten vorliegen haben: Gegeben ist eine Permutation von Zahlen 1 .. N, nicht eine beliebige Zahlenfolge. <\/p>\n Ich werde mal einige Untersuchungen durchf\u00fchren und die Ergebnisse an dieser Stelle ver\u00f6ffentlichen.<\/p>\n <\/p>\n Update 03.11.2005<\/strong>: Ich habe drei Algorithmen untersucht: BubbleSort, SelectionSort und QuickSort.<\/p>\n Den Standard-BubbleSort-Algorithmus habe modifiziert, s.d. die Liste vorw\u00e4rt und r\u00fcckw\u00e4rts durchschritten wird – da die Distanz zwischen zwei Vertauschungen wichtig ist, hilft dies, diese Distanzen zu veringern.<\/p>\n W\u00e4hrend ich SelectionSort aus dem Lehrbuch angewendet habe, ist meine Quicksort-Implementierung mit den „\u00fcblichen“ Optimierungen versehen: f\u00fcr kleine Teilmengen wird SelectionSort angewendet. Die Wahl des Pivot-Elementes ist einfach, da die Positionsnummer mit dem Wert zusammenf\u00e4llt und damit immer der „mittlere“ Wert einer Liste genommen werden kann.<\/p>\n Zu den Ergebnissen:<\/strong> BubbleSort bleibt am wenigsten effizient. SelectionSort und QuickSort liefern sich ein Kopf-an-Kopf-Rennen, wobei es darauf ankommt, ab welcher Listenl\u00e4nge QuickSort auf SelectionSort zur\u00fcckf\u00e4llt.<\/p>\n Wie folgendes Diagramm zeigt, „gewinnt“ BubbleSort gegen SelectionSort ziemlich unabh\u00e4ngig von der Anzahl der Kan\u00e4le: der durchschnittliche Rang betr\u00e4gt 1,8 (Rang 1 f\u00fcr den Gewinner, Rang 2 f\u00fcr den Verlierer, bei 2000 zuf\u00e4lligen Kanalbelegungen). Beim Rennen SelectionSort gegen QuickSort ist der Ausgang abh\u00e4ngig von der Anzahl der Kan\u00e4le sowie dem Schwellwert, ab dem Quicksort in SelectionSort \u00fcbergeht. Mit zunehmender Anzahl von Kan\u00e4len wird Quicksort st\u00e4rker, bei ca. 39 Kan\u00e4len gibt es im Mittel ein „Unentschieden“. Der Einfluss des genannten Schwellwertes l\u00e4\u00dft sich schlecht beschreiben. Das folgende Diagramm zeigt eine „Draufsicht“ auf ein 3D-Diagramm. Die X-Koordinate ist der genannte Schwellwert, die Y-Koordinate die Anzahl der Kan\u00e4le. Die Farbe kodiert den mittleren Rang. Alles „ab“ orange (und „h\u00f6her“) stellt den Gewinn (im Mittel) f\u00fcr QuickSort dar. Die blaue Fl\u00e4che rechts der Diagonale steht „keine Messung“, da dort der Schwellwert h\u00f6her als die H\u00e4lfte der Anzahl der Kan\u00e4le liegt. Es bleibt die Frage, ob es einen anderen, g\u00fcnstigeren Algorithmus gibt.<\/p>\n
\n![\"BubbleSort](\"http:\/\/www.epischel.de\/wordpress\/wp-content\/ks-bs-vs-ss.png\")
<\/p>\n
\n![\"SelectionSort](\"http:\/\/www.epischel.de\/wordpress\/wp-content\/ks-ss-vs-qs.png\")
\nEs scheint also so zu sein, dass eine „Vorsortierung“ mittels Quicksort desto vorteilhafter ist, je gr\u00f6\u00dfer die Anzahl der Kan\u00e4le.<\/p>\n