Mit dem Laden des Videos akzeptieren Sie die Datenschutzerklärung von YouTube.
Mehr erfahren
In diesem Video wird anhand der Sortierung einer Buchlieferung von 1.280 Büchern an eine Bibliothek dargestellt, wie die 3 Sortieralgorithmen Bubble Sort, Insertion Sort und Quick Sort funktionieren. Die Aufgabe: Der Bibliothekar soll 1.280 Bücher so rasch als möglich alphabetisch sortieren.
Im ersten Verfahren wird jedes Buch mit seinem Nachbarn auf der linken Seite verglichen. Ist das rechte Buch im Alphabet früher angesiedelt als das linke, werden deren Plätze vertauscht. Der Prozess wird solange wiederholt, bis es kein Buch mehr gibt, zu dessen Linken sich ein im Alphabet nachgestelltes Buch befindet. Diese Form der Sortierung wird „Bubble Sort“ genannt und benötigt für alle 1.280 Bücher 818.560 Vergleiche. Bubble Sort ist einfach, aber enorm Zeitaufwändig, weil fast alle Bücher mit fast allen anderen verglichen werden.
Das zweite Verfahren – Insertion Sort – beginnt zwar gleich wie das Bubble Sort-Verfahren, doch wird der Vergleich nach links hin fortgesetzt. Wenn das Buch an Position 5 im Alphabet dem Buch an der Position 4 im Alphabet vorangestellt ist, so werden die Positionen der beiden vertauscht. Hier hört der Vergleich aber nicht auf, denn das Buch wird auch gleich mit den Büchern auf den Positionen 1-3 vergleichen und auch gleich korrekt einsortiert. Dieses Verfahren reduziert die Anzahl der Vergleiche um die Hälfte, also auf 409.280.
Die dritte und effizienteste Methode ist das QuickSort-Verfahren. Hierbei wird irgendein Buch aus der Mitte ausgewählt. Von diesem Buch ausgehend, werden alle im Alphabet nachgestellten Titel rechts von dem Buch angeordnet, die im Alphabet vorangestellten links davon. Die zwei nun entstandenen Blöcke werden abermals jeweils halbiert und innerhalb der beiden Hälften wird ebenso nach im Alphabet vorangestellt oder nachgestellt sortiert. Die QuickSort-Methode ermöglicht es, die direkten Vergleiche auf ein Minimum zu reduzieren, weil große Gruppen von Büchern auf einmal miteinander verglichen werden. Mit dieser Methode wird die Anzahl der Vergleiche auf 11.776 reduziert. Das sind etwa eineinhalb Prozent der Menge des Bubble Sort-Verfahrens!