07.06.2019Wenn Sie meine Seite zu Quicksort kennen, haben Sie bereits einen wichtigen Algorithmus zum Sortieren von Zahlen gesehen. Diese Seite zeigt einige einfachere, teilweise intuitivere aber im Allgemeinen auch langsamere Algorithmen für das Sortieren eines Arrays. Sie sind so einfach, dass es keine separate Seite braucht um sie zu zeigen, also sind sie alle hier zusammengefasst. Wir werden uns ‘Bubblesort’, ‘Insertionsort’, ‘Selectionsort’, ‘Countingsort’ und ‘Bucketsort’ ansehen. In jedem Fall wird zu einer aufsteigenden Ordnung sortiert, womit die größten Elemente am rechten Ende platziert werden. Alternativ könnte man auch eine absteigende Sortierung vornehmen, was zur umgekehrten Reihenfolge führen würde.
Der Name von Bubblesort kommt aus dem Englischen (‘bubbles’ sind Bläschen) und rührt daher, dass die Elemente beim Sortieren nach oben, also zu größeren Zahlen hin, aufblubbern. Wir fangen also am Anfang des Arrays an und vergleichen die ersten beiden Zahlen. Falls die erste größer ist als die zweite, werden sie vertauscht. Oben werden die zu vergleichenden Zahlen durch die grünen Säulen gezeigt. Die größere der beiden Zahlen wird dann mit dem nächsten Wert im Array verglichen. Es werden also weiter Zahlen verglichen und möglicherweise vertauscht, bis der größte Wert am Ende des Arrays steht. Dann fängt der Algorithmus wieder am Anfang an. Als Optimierung merkt sich das Programm die Ausdehnung des teilsortierten Endes, hier durch grüne Kästchen markiert, und wenn der Eintrag dort ankommt hat er seinen Platz gefunden.
Insertionsort (engl. ‘insert’ - einfügen) sieht Bubblesort ähnlich, ist aber ein ganz anderer Algorithmus und funktioniert auch anders. Insertionsort hat mit Bubblesort gemein, dass die linke Seite des Arrays noch unsortiert ist, während die rechte Seite bereits teilweise sortiert ist. Die rechte Seite wächst also von Null ins ganze Array, und dann ist die Sortierung fertig. Damit das sortierte Ende wächst, wird das letzte unsortierte Element so lange mit den folgenden Elementen vertauscht bis es an die richtige Position gelangt. So kommt es an die richtige Stelle.
Wenn jemand gebeten wird einen Sortieralgorithmus zu erfinden denken sie sich oft zuerst so etwas wie Selectionsort aus (engl. ‘select’ - auswählen): der nächstgrößere Wert wird wiederholt ausgewählt und durch tauschen an einen neuen Platz am Ende des Arrays gebracht. Die Auswahl des größten Elementes wird ganz einfach mit durchlaufen des unsortierten Teils gemacht. Der Durchlauf ist durch die grüne Säule dargestellt, der aktuell größte Wert durch eine blaue Säule. Wie zuvor wir der bereits sortierte Teil des Arrays durch den grünen Hintergrund der Kästchen dargestellt.
Die bisher hier verwendeten Methoden sind vergleichsbasierte Methoden. Sie funktionieren indem sie Einträge im Array vergleichen und je nach Ausgang des Vergleichs vertauschen oder nicht. Der Countingsort Algorithmus ist anders. Die Sortierung basiert hier auf den Absolutwerten der Einträge. Sie funktioniert indem die Anzahl (engl. ‘count’) des Vorkommens der Werte ausgezählt werden, dann wird die richtige Position im sortierten Array aus den Anzahlen abgeleitet. Dies funktioniert am besten wenn die Zahl der unterschiedlichen Werte nicht zu groß ist, für dieses Beispiel haben wir also nur Werte zwischen 1 und 31 gewählt. Die Animation oben zeigt wie das Eingabearray einmal durchlaufen wird um die Anzahlen zu bestimmen. Um den ganzen Algorithmus beim sortieren zu sehen, schauen Sie aufs nächste Panel.
Die zweite Phase des Coutingsort durchläuft die Anzahlen im unteren Array und platziert die richte Zahl an Einträgen in das leere Array, um es zu sortieren. Wegen der Korrespondenz zwischen den Anzahlen (unten) und dem Array (oben) kann die Sortierung funktionieren. Diese Methode erscheint schnell, und ist es in der Tat auch. Aber es waren Einschränkungen nötig damit sie gut funktioniert, so wie die geringe Anzahl an unterschiedlichen Werten im Eingabearray. Wir werden eine weitere Sortiermethode unten betrachten, Bucketsort, die auf diese Einschränkung verzichten kann, aber sonst ähnlich funktioniert.
Bucketsort platziert jedes Element des Arrays in einen Eimer (engl. ‘bucket’). Der richtige Bucket wird aus dem Wert selbst, der Anzahl an Buckets und der erwarteten Bandbreite an Werten berechnet. Wieviele Buckets benutzt werden ist eine Stellschraube des Algorithmus. Die Hauptannahme bei Bucketsort ist das die Werte mehr oder weniger gleich verteilt sind, so dass sie nicht alle im selben Bucket landen. Nachdem das Array so aufgeteilt worden ist, müssen die Werte innerhalb von jedem Bucket nochmal sortiert werden. Dies kann parallel gemacht werden und ist oft recht schnell da nur wenige Werte in jedem Bucket sind. Der letzte Schritt ist dann noch, alle Werte aus den verschiedenen Buckets ins alte Array zu verketten. Et voilà!
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken. Und wer immer noch nicht genug vom Sortieren hat, die Seite über den Heap enthält ein Panel über Heapsort, noch einem Sortieralgorithmus.