Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Überblick Sortierverfahren 1
Das Wichtigste aus dem Video
Transkriptautomatisch erstellt · 51 Zeilen
- Ihr kennt das sicher: Ihr steht vor eurem fetten Tresor und müsst die Geheimnummer richtisch sortiert eingeben.
- Ihr kommt aber einfach nicht drauf, wie man diese Zahlen sortieren kann. So ein Mist aber auch!!
- Immer diese Zahlen…. Gott sei Dank gibt es da die Sortierverfahren!
- Verschaffen wir uns mal ein Überblick über die freshen Dinger. Okidoki!
- Was sind jetzt also Sortierverfahren? Sortierverfahren sind Algorithmen die uns helfen eine gegebene Menge von Objekten in
- eine bestimmte Reihenfolge zu bringen. Das können dann Zahlen, Buchstaben, Wörter usw. sein.
- Meistens bekommen wir einfach ein Array mit irgendwelchen Zahlen hingeklatscht und müssen diese dann aufsteigend oder absteigend sortieren.
- Jetzt fragt ihr euch bestimmt: Aha cool und wo brauch ich sowas im echten Leben?
- Diese Algorithmen werden tatsächlich oft verwendet: Zum Beispiel wenn ihr nach dem Zeitpunkt der zuletzt gehörten Musik sucht,
- oder wenn ihr eure letzten Malle Bilder nach Datum sortiert. Also praktisch überall dort, wo ihr irgendwas sortieren müsst oder wo ihr ein Filter einsetzt.
- Macht Sinn oder? Wie ihr euch denken könnt, gibt es nicht nur einen universal Sortieralgorithmus, sondern
- ganz ganz ganz viele. Die Sortierverfahren kann man nach verschiedene Kategorien bewerten.
- Zum Beispiel nach ihrem Speicherplatzbedarf. Genauer bedeutet das ob die Verfahren interne oder externe Sortieralgorithmen sind.
- Beim internen Sortierverfahren passen alle Daten in den Speicher. Das heißt der Algorithmus kann innerhalb des Hauptspeichers stattfinden.
- Meist werden damit einfache Arrays sortiert. Beim externen Sortieren sind die Datensätze zu groß für den Speicher und müssen aufgeteilt
- werden. Dafür können dann externe Speicherquellen, wie Festplatten oder sowas, verwendet werden.
- Sinnvoll wenn man große Datenmengen sortieren möchte. Man kann sich merken: Internes Sortierverfahren: Alle Objekte sind
- bekannt Externes Sortierverfahren: Zu jedem Zeitpunkt ist nur ein Teil der Objekte bekannt.
- Sortierverfahren können auch Stabil oder instabil sein. Stabil bedeutet die relative Reihenfolge der Elemente mit gleichen Schlüsselwerten bleibt
- erhalten. Hä?
- Wat laberscht du? Zum Beispiel sortieren wir erst Oma’s nach dem Alphabet.
- Hier seht ihr die 4 Ommmas, und die sind nach ihrem Anfangsbuchstaben sortiert: A, B, C dann D.
- Jetzt wollen wir aber nach der orthopädischen Schuhgröße - die Zahl unten - sortieren. Machen wir :)
- Jetzt seht ihr, jop unten ist es richtig sortiert. Und die Omas, die die gleiche Schuhgröße haben, die sind weiterhin auch alphabetisch
- sortiert! Bei Schuhgröße 20 ist Oma A immer noch vor Oma B.
- Deswegen wär das hier STABIL. Also bei den stabilen Sortierverfahren ändert sich bei gleichen Werten die Reihenfolge der
- vorherigen Sortierung nicht. Macht Sinn oder?
- Instabile Sortierverfahren können diese relative Reihenfolge nicht garantieren. Die Kategorie, die beim Vergleich immer herangezogen wird ist die Laufzeit.
- Das bedeutet wie schnell ist der jeweilige Algorithmus beim sortieren. Dat ganze wir aber nicht mit Zeiteinheiten gemessen...Das heißt vergleiche mit Usain
- Bolt sind nicht so einfach :D In der Informatik misst man die Laufzeit mit der Landau Notation.
- Hä Whaat? Das heißt wir messen die Anzahl der Elementarschritte in Abhängigkeit der eingegebenen Variablen.
- Einfach gesagt: Wie viel Schritte sind bei so und so vielen eingegebenen Variablen nötig um ans Ziel zu gelangen.
- Dabei werden nur die elementaren Schritte betrachtet. Geschrieben wir dat ganze dann mit diesem O.
- Zum Beispiel bedeutet O(n) lineares Wachstum. Das heißt die Zeit die der Algorithmus braucht wächst konstant.
- O(n^2) ist dann das quadratische Wachstum. usw.
- Dabei unterscheidet man noch die vergleichsbasierten und nicht vergleichsbasierten Algorithmen. Vergleichsbasiert bedeutet: Die Elemente werden paarweise verglichen und dann sortiert.
- Deswegen kann man bei den vergleichsbasierten Verfahren noch den Best Case, den Average Case und den Worst Case messen.
- Hat damit zu tun, dass die Elemente ja schon vorher unterschiedlich gut vorsortiert sein können.
- Und wenn die Elemente vorher schon gut vorsortiert sind, dann ist der Algorithmus auch schneller fertig :)
- Nicht vergleichsbasiert sind dagegeen dann alle Algorithmen, bei denen die Werte nicht direkt verglichen werden.
- Neben diesen Kategorien kann man sich noch tausend andere ausdenken: Zum Beispiel ob ein Sortierverfahren leicht oder schwer zu programmieren ist….Wie einfach
- er vom Prinzip ist und und und…. In den folgenden Videos zu den einzelnen Verfahren, werden wir immer etwas zur Laufzeit, Stabilität
- und Art des Sortierverfahrens sagen. Bevor ihr euch aber auf die Videos stürzt.
- Fassen wir nochmal zusammen: Sortierverfahren sind also Algorithmen, die Objekte in eine gewisse Reihenfolge bringen
- können. Unterscheiden kann man diese anhand verschieden Kriterien.
- So gibt es interne und externe Sortierverfahren. Intern bedeutet alles passt in den Speicher Extern bedeutet wir müssen etwas auslagern.
- Sortierverfahren können Stabil oder Instabil sein. Stabil heißt bei neu Sortierung bleibt die relative Reihenfolge der vorherigen gleich.
- Wollen wir die Dinger miteinander vergleichen nutzen wir die Laufzeit. Diese wird gemessen in der Landau Notation.
- Heißt: wir messen die elementaren Schritte bis zum Ziel in Abhängigkeit der eingegebenen Werte.
- Ja jut Freunde, dann fetzt euch mal die ganzen geilen Sortierverfahren rein oder geht auf die Lernplattform.
- Oder macht doch was ihr wollt. Haut rein bis gleich.