Am 14. September 2017 haben wir eine überarbeitete Fassung unserer Datenschutzrichtlinie veröffentlicht. Wenn Sie video2brain.com weiterhin nutzen, erklären Sie sich mit diesem überarbeiteten Dokument einverstanden. Bitte lesen Sie es deshalb sorgfältig durch.

Mathematik-Grundbegriffe für Programmierer

Sortieralgorithmen – Bubble-Sort und Quick-Sort

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Sortieralgorithmen dienen dazu, die Elemente einer Menge (z. B. eines Arrays) nach einem bestimmten Kriterium zu sortieren. Voraussetzung für die Sortierung ist, dass die Elemente nach irgendeinem Kriterium vergleichbar sind. Das kann z. B. ein ganz einfacher Zahlenvergleich oder ein komplizierter Vergleich von Strukturelementen sein. Die verschiedenen Sortieralgorithmen unterscheiden sich durch unterschiedliche Ausführungsgeschwindigkeiten. Die Ausführungsgeschwindigkeit hängt davon ab, wie viele Vergleiche und wie viele Vertauschungen stattfinden müssen. Das Video stellt zwei Sortieralgorithmen vor: Bubble-Sort und Quick-Sort.
05:35

Transkript

Zu den bekannten und häufig gebrauchten Algorithmen zählen die Sortieralgorithmen. Sie haben im wesentlichen alle das gleiche Ziel, nämlich eine Menge an vorher unsortierten Daten nach einem bestimmten Kriterium zu sortieren. Nach dem Sortieren liegen die Elemente einer Datenstruktur in einer aufsteigenden oder absteigenden Reihenfolge vor. Damit man so was machen kann, müssen die Elemente allerdings nach gewissen Kriterien vergleichbar sein. Zahlen, wie sie hier vorliegen, in einem Array, die sind beispielsweise vergleichbar, auf größer oder kleiner. Es muss sich allerdings nicht um einen einfachen Zahlenvergleich handeln - wie wir es ja auch in diesem Beispiel machen werden. Es kann auch ein komplizierter Vergleich sein. Aber die Art des Vergleiches ist vollkommen irrelevant für den Sortieralgorithmus selbst. Die verschiedenen Sortieralgorithmen unterscheiden sich im Wesentlichen durch die Ausführungsgeschwindigkeit. Die Ausführungsgeschwindigkeit hängt davon ab, wie viele Vergleiche notwendig sind und wie viele Vertauschungen stattfinden müssen. Denn Sie sehen hier, dass Vertauschungen stattfinden. Auch wenn Sie kein Java kennen, hier wird ein Feldinhalt an der Position "j" durch den Feldinhalt an der Position "j+1" ersetzt. Und der Feldinhalt an der Position "j+1" wird durch den bisherigen Inhalt an der Position "j" ersetzt. Was sie hier sehen, ist ein Java-Programm, das den sogenannten "Bubble-Sort" implementiert. Dabei werden jeweils zwei benachbarte Elemente verglichen. Das sehen sie hier. Wenn das linke Element größer ist, als das rechte, werden sie vertauscht. Dabei beginnt man immer mit dem ersten und dem zweiten Element. Dann werden das zweite und das dritte Element verglichen, danach das dritte und das vierte, und so weiter, bis zum Ende des Arrays. Die Folge ist, dass das größte Element ans Ende des Arrays wandert. Wir lassen das Beispiel mal laufen und sie sehen, dass dieses Array nun sortiert ist. Der entscheidende Punkt ist: Diese Schritte - deswegen haben wir hier auch zwei Schleifen - werden so lange wiederholt, bis das vorletzte Element erreicht ist. Das letzte Element ist bereits sortiert, denn es ist nach dem ersten Durchlauf das größte Element des Arrays. Danach steht das zweitgrößte Element auf der vorletzten Position, und die letzten beiden Elemente des Array sind also sortiert. Und dann führt man diese Schritte so lange durch, bis auch das letzte Element in der Sortierung passt. Dieser Algorithmus ist offensichtlich sehr aufwendig und damit nicht allzu schnell. Dieser Name "Bubble-Sort" kommt übrigens daher, dass die kleinen Elemente wie eine Blase nach oben steigen, also nach vorne wandern. Oder umgekehrt kann man auch sehen: Die großen Elemente steigen wie Blasen nach hinten in der Datenstruktur. Es gibt, wie gesagt, noch eine ganze Reihe an weiteren Sortieralgorithmen. Etwa der sogenannte "Shell-Sort" oder auch der "Quick-Sort" für den hier noch ein Beispiel zur Verfügung steht. Der "Quick-Sort" ist wahrscheinlich der am häufigsten verwendete Sortieralgorithmus. Dabei wird eine Datenstruktur in zwei Teile zerlegt, die in einer gewissen Weise vorsortiert sind. Es gibt ein Teilfeld mit kleineren Elementen, und es gibt ein Teilfeld mit größeren Elementen, nach der Sortierung. Um so etwas einschätzen zu können, braucht man ein Element als Vergleichselement und das muss an die richtige Stelle im Array geschoben werden. Alle Elemente die kleiner sind als dieses Vergleichselement, werden in das linke Teil-Array verschoben, die größten Elemente kommen in das rechte Teil-Array. Ein bisschen erinnert das an die "binary search" bei Suchalgorithmen. Nach der Einsortierung steht das einsortierte Element an der richtigen Stelle und wird nicht mehr weiter beachtet. Die beiden Teil-Arrays, links und rechts von diesem Element, werden dann aber nach dem gleichen Prinzip weiterverarbeitet. Lassen sie uns noch einen kurzen Blick auf den Code hier werfen, der diesen "Quick-Sort"-Algorithmus ausführt. Ich starte mal das Programm. Und sie sehen, ich habe hier ein sortiertes Array und das ursprüngliche Array ist offensichtlich unsortiert. Ich starte mit einem Testwert 5 und fange an, den Algorithmus in verschachtelten Schleifen abzuarbeiten. Dabei vergleiche ich jeweils die Größe der Elemente in dem Array, beziehungsweise in den Teil-Arrays. Sie haben also in diesem Video grundsätzliche Sortieralgorithmen kennengelernt und als Beispiele den "Bubbel-Sort" und in einem Überblick den "Quick-Sort".

Mathematik-Grundbegriffe für Programmierer

Lernen Sie die Themenbereiche und Verfahren aus der Mathematik kennen, die bei der täglichen Programmierarbeit zum Einsatz kommen.

2 Std. 54 min (40 Videos)
Derzeit sind keine Feedbacks vorhanden...
 
Exklusiv für Abo-Kunden
Erscheinungsdatum:04.10.2016
Aktualisiert am:19.12.2016

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!