Quick Sort: Informatik (sehr allgemein)
bleeptrack
https://www.youtube.com/watch?v=UoJJ78K-uc0

Transkript (automatisch erstellt)

0:02 hi schön dass du da bist ich mache heute weiter mit den Sortieralgorithmen und heute möchte ich den Quicksort zeigen hier die schön bekannte
0:12 Zahlenfolge benutzen wir wieder zum Sortieren und es ist jetzt so dass der Quicksort oft ein bisschen unterschiedlich erklärt wird denn man
0:20 muss zuerst ein sogenanntes Pivotelement wählen ein Element das man später zum Sortieren braucht und das wählt man aus der aus den vorhandenen zahlen und wie
0:30 man das wählt das kann ganz unterschiedlich sein man könnte die erste Zahl nehmen man könnte immer die letzte Zahl nehmen oder zufällig was
0:37 ziehen ja das wird unterschiedlich gemacht und zum Erklären heute würde ich vorschlagen dass wir die erste Zahl benutzen das wäre in unserem Fall die
0:47 fünf und die schreibe ich schon mal in die Mitte so
0:55 F was wir jetzt machen wir haben ein Pivotelement gezogen das ist rot markiert und alle anderen Zahlen also ausgenommen
1:04 der fünf werden jetzt sortiert je nachdem ob sie kleiner oder größer sind als die fünf kommen Sie links oder rechts neben die fünf wir fangen gleich
1:11 an die neun ist größer muss also rechts von der fünf stehen die ein ist kleiner die vier ist kleiner die sechs ist größer die sieben ist größer die D ist
1:22 kleiner die zwei ist kleiner und die a ist größer so jetzt sind zwei Hälften entstanden wir haben hier links eine zahlenhälfte und hier rechts in schwarz
1:33 und diese zahlenhälften werden jetzt mit dem gleichen Verfahren behandelt das heißt aus jedem dieser Zahlenreihen wird wieder ein Pivotelement gezogen es wird
1:42 wieder genuso sortiert das heißt hier raus ziehen wir das Pivotelement wir haben gesagt wir nehmen immer die erste Zahl also die
1:52 1 ich schreibbe ich mal hierhin und hier nehmen wir auch die erste Zahl raus das wäre die ne und jetzt werden wieder die restlichen zahlen einfach einsortiert
2:04 das heißt die 4 ist größer die 3 ist größer und die Z ist größer und hier die SE ist kleiner die 7ben ist kleiner und die a ist
2:15 kleiner jetzt sind nur zwei Zahlen Folgen entstanden bei dieser Aktion es hätten mehr sein können denn wenn Zahlen kleiner gewesen wären als die ein hätten
2:23 wir hier links noch was stehen gehabt und wenn welche Größe gewesen wären als die neuen hätten wir hier rechts auch noch was stehen gehabt in unserem Fall
2:29 nicht und wir machen einfach weiter aus dieser Zahlenfolge machen wir das gleiche wieder die vi ist unser
2:38 nächstes Pivotelement und die 3 und 2 werden sortiert sind beide kleiner landen also hier hier ist das nächste Pivotelement
2:49 die 6 und die 7 und 8 werden sortiert und beide größer landen also hier und weiter geht's sind wieder nur zwei entstanden hätten auch wieder mehr
3:03 deutlich mehr sein können mehr zahlenteile und ihr seht schon es wird jetzt sehr klein wir sind also praktisch fast fertig die D ist das nächste
3:12 Pivotelement und die Z muss nur noch sortiert werden die ist kleiner also muss sie links davon stehen und hier ist die 7 das
3:21 Pivotelement die a ist größer muss also rechts davon und jetzt sind jeweils nur noch einzelne Zahlen ü
3:30 die werden jetzt zum Pivotelement auch natürlich bleibt ja auch nichts anderes übrig und es sind jetzt aber keine Zahlen zum einsortieren mehr da und
3:39 daran kann man erkennen dass der Algorithmus zu Ende ist und sortiert haben wir jetzt indem wir alle pivotelemente einfach mal nach unten
3:48 ziehen das heißt wir ziehen die eins hier runter die D hier runter die vier landet hier die
3:56 F die SE und ihr seht schon es entsteht eine sortierte Zahlenfolge das war schon der
4:08 Quicksort und damit ihr auch mal probieren könnt habe ich hier eine Zahlenfolge für euch mit der macht ihr das gleiche nehmt auch immer das erste
4:17 Element als Pivotelement schreibt es auf die Lösung gibt's wie immer unter dem Video ich hoffe es hat euch was gebracht und es hat euch gefallen schaut euch
4:25 auch gerne andere Videos von mir an ja und ich wünsche euch alles Gute tschüss ich mach das noch mal das ist scheiße das ist schiter wir erklären das
4:42 noch mal von vorne gefund