Überblick Sortierverfahren 1
Informatik - simpleclub
https://www.youtube.com/watch?v=RbWVUPS8_JY

Transkript (automatisch erstellt)

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