Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Überblick Sortierverfahren 1
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
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.
Zum Nachlesen
SortierverfahrenUnter einem Sortierverfahren versteht man in der Informatik einen Algorithmus, der dazu dient, ein Tupel (i. Allg. ein Array) zu sortieren.
GnomesortGnomesort ist ein sehr einfacher und stabiler Sortieralgorithmus. Animation von Insertionsort bzw. von Gnomesort ohne Visualisierung der …
BubblesortBubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert.
Stabilität (Sortierverfahren)Ein stabiles Sortierverfahren ist ein Sortieralgorithmus, der die Reihenfolge der Datensätze, deren Sortierschlüssel gleich sind, bewahrt.