Wir haben letztens unseren defekten Videorekorder durch einen neuen ersetzt. Nun stand ich vor dem Problem, alle Kanäle so einzuspeichern wie auf dem Fernseher. Ich habe mich dafür entschieden, einen automatischen Sendersuchlauf durchzuführen und dann mit der vorhandenen Funktion „2 Kanäle vertauschen“ alle Kanäle an ihren richtigen Platz zu bewegen.
Welcher Algorithmus ist hier der beste? Gegeben sei eine unsortierte Liste von Zahlen (die Zahl steht für die entgültige Senderplatzierung) sowie eine Vergleichsfunktion und eine Funktion zum Vertauschen von zwei Kanalplätzen. Gesucht ist der günstigste Algorithmus, um die Zahlen zu sortieren. Günstig meint minimal bzgl. der Summe der Distanzen, über die Kanäle vertauscht werden. Die Distanzen sind deshalb wichtig, weil ich auf der Fernbedienung entsprechend oft „vor“ bzw. „zurück“ drücken muss. Dies sollte minimal sein.
Die erste Idee ist natürlich, die klassischen Suchalgorithmen zu untersuchen. Ich bin nach Selection Sort vorgegangen. Quicksort fällt mir ein, weil dort auch Elemente vertauscht werden. Auch Bubble Sort nicht vergessen, weil dort nur benachbarte Elemente vertauscht werden, die Distanz also immer 1 ist.
Vielleicht gibt es einen anderen günstigen Algorithmus, weil wir hier ja Besonderheiten vorliegen haben: Gegeben ist eine Permutation von Zahlen 1 .. N, nicht eine beliebige Zahlenfolge.
Ich werde mal einige Untersuchungen durchführen und die Ergebnisse an dieser Stelle veröffentlichen.
Update 03.11.2005: Ich habe drei Algorithmen untersucht: BubbleSort, SelectionSort und QuickSort.
Den Standard-BubbleSort-Algorithmus habe modifiziert, s.d. die Liste vorwärt und rückwärts durchschritten wird – da die Distanz zwischen zwei Vertauschungen wichtig ist, hilft dies, diese Distanzen zu veringern.
Während ich SelectionSort aus dem Lehrbuch angewendet habe, ist meine Quicksort-Implementierung mit den „üblichen“ Optimierungen versehen: für kleine Teilmengen wird SelectionSort angewendet. Die Wahl des Pivot-Elementes ist einfach, da die Positionsnummer mit dem Wert zusammenfällt und damit immer der „mittlere“ Wert einer Liste genommen werden kann.
Zu den Ergebnissen: BubbleSort bleibt am wenigsten effizient. SelectionSort und QuickSort liefern sich ein Kopf-an-Kopf-Rennen, wobei es darauf ankommt, ab welcher Listenlänge QuickSort auf SelectionSort zurückfällt.
Wie folgendes Diagramm zeigt, „gewinnt“ BubbleSort gegen SelectionSort ziemlich unabhängig von der Anzahl der Kanäle: der durchschnittliche Rang beträgt 1,8 (Rang 1 für den Gewinner, Rang 2 für den Verlierer, bei 2000 zufälligen Kanalbelegungen).
Beim Rennen SelectionSort gegen QuickSort ist der Ausgang abhängig von der Anzahl der Kanäle sowie dem Schwellwert, ab dem Quicksort in SelectionSort übergeht. Mit zunehmender Anzahl von Kanälen wird Quicksort stärker, bei ca. 39 Kanälen gibt es im Mittel ein „Unentschieden“. Der Einfluss des genannten Schwellwertes läßt 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äle. Die Farbe kodiert den mittleren Rang. Alles „ab“ orange (und „höher“) stellt den Gewinn (im Mittel) für QuickSort dar. Die blaue Fläche rechts der Diagonale steht „keine Messung“, da dort der Schwellwert höher als die Hälfte der Anzahl der Kanäle liegt.
Es scheint also so zu sein, dass eine „Vorsortierung“ mittels Quicksort desto vorteilhafter ist, je größer die Anzahl der Kanäle.
Es bleibt die Frage, ob es einen anderen, günstigeren Algorithmus gibt.