00:00:00
[Musik]
00:00:11
[Musik]
00:00:13
also herzlich willkommen verändert west
00:00:17
das thema heute ist das untier frank
00:00:19
wixforth kriegs ort galt lange zeit als
00:00:22
das schmerze bekannte sortiert verfahren
00:00:24
wurde dann 2009 abgelöst vom dual
00:00:27
bookrix ort von vladimir jahres last ist
00:00:31
im übrigen auch das standard ihr
00:00:33
verfahren weile in der
00:00:34
programmiersprache java
00:00:36
ja aber zu sagen das ist das schnellste
00:00:39
tier verfahren das ist gefährlich das
00:00:41
werde ich auch immer wieder in meinen
00:00:43
vorlesungen fragt warum müssen wir diese
00:00:45
ganzen sortiere verfahren lernen reicht
00:00:47
es nicht diesen einen schnellsten zu
00:00:49
können deswegen ist eigentlich man kann
00:00:51
es nicht pauschal beantworten das ist
00:00:52
immer der schnellste sortiert muss das
00:00:54
geht nicht das hängt von zu vielen
00:00:56
faktoren ab zuallererst natürlich wie
00:00:59
viele eingabe werte gilt es zu sortieren
00:01:01
ja muss ich 10 oder 100 werte mit
00:01:03
anderen vergleichen und sortieren was
00:01:05
macht eigentlich keinen unterschied ob
00:01:07
ich in babbels fort mit der
00:01:08
quadratischen laufzeit benutzt oder
00:01:10
einen workshop wixforth und lineal
00:01:13
logarithmische laufzeit haben wobei der
00:01:15
kriegskosten übrigen auch mal
00:01:16
quadratisch werden kann kommt aber
00:01:18
gleich zu sortiere ich aber wenn ich
00:01:21
eine million oder 10 millionen werte
00:01:22
dann macht natürlich einen enormen
00:01:23
unterschied
00:01:25
einer quadratischen sortierten rhythmus
00:01:28
wieder in paris ort benutze oder einen
00:01:30
linear logarithmischen wieder works aus
00:01:31
den kriegs ort was ist noch entscheidend
00:01:34
weil ich vergleicht nicht immer nur in
00:01:36
deutscher werte miteinander manchmal
00:01:38
kann es sein dass komplexe darf
00:01:40
miteinander vergleichen muss zum
00:01:42
beispiel datensätze oder komplexe
00:01:45
objekte
00:01:45
das heißt er vergleich alleine ist schon
00:01:48
sehr zeitaufwendig und dann wäre es
00:01:51
natürlich sinnvoll einsortieren
00:01:52
verfahren einzusetzen
00:01:53
mit möglichst wenigen vergleich
00:01:55
operation so was wieder wasser abtrieb
00:01:58
so zum beispiel
00:02:00
und wir werden darauf wieder fix ort
00:02:03
eigentlich genau funktioniert der
00:02:05
arbeitet nach dem sogenannten die reihe
00:02:07
kommt prinzip teile und herrsche
00:02:10
das heißt wir haben jetzt ein reh als
00:02:13
eingabe menge dass unsere teams und das
00:02:15
wird jetzt immer geteilt und beim
00:02:17
aufteilen wird schon immer eine ein
00:02:20
element sogenannte pico element an die
00:02:22
richtige position gesetzt dieses pivot
00:02:25
element ist also ein element aus dem
00:02:27
harry zugs element das wird jetzt immer
00:02:30
für jeden durchgang als orientierung
00:02:32
herangezogen so dass sämtliche werte die
00:02:35
kleiner sind als piero element auf die
00:02:37
eine seite von der endgültigen position
00:02:40
kommen und die werte die größer sind auf
00:02:43
die rechte seite auf die andere seite
00:02:45
von dem elend das heißt am ende eines
00:02:49
durchgangs steht immer das pico element
00:02:51
in der mitte im optimalen fall in der
00:02:53
mitte und teilt aus eric in zwei gleich
00:02:56
große hälften auf links und rechts das
00:02:58
wäre optimal fall allerdings kann man
00:03:00
das nicht immer garantieren dass das pro
00:03:02
element tatsächlich immer genau der
00:03:05
median ist und in der mitte landet denn
00:03:07
er müsste ich ja erst bestimmen den
00:03:09
median und das kostet mich ein
00:03:11
konstanter faktor mehr zeit hat sich in
00:03:14
der praxis als nicht gut erwiesen es
00:03:16
gibt im prinzip drei möglichkeiten das
00:03:18
parlament zu wählen das erste wäre man
00:03:21
nimmt immer den ersten berg aus dem er
00:03:23
sagt da werden index 0 dass es mal
00:03:27
brennt kann gefährlich werden warum ist
00:03:31
das erinnere mich schon vorsortiert
00:03:32
block komplett sortiert kriege ich
00:03:35
quadratische laufzeit warum weil man
00:03:38
tiefer element steht immer ganz toll
00:03:39
linken rand und ich teile meine ich gar
00:03:43
nicht so richtig aus weil ich
00:03:44
positioniere immer nur mit der komplette
00:03:47
rest ist es das neue teil
00:03:49
viel schöner wäre es natürlich wenn ich
00:03:52
das parlament immer genau in der mitte
00:03:54
positionieren kann denn dann für zwei
00:03:56
gleiche teilen race die ich dann re
00:03:59
kursiv sortieren kann die
00:04:01
wahrscheinlichkeit
00:04:02
dass ich nicht diese ungünstigen fall
00:04:05
bekomme wächst wenn ich ein parlament
00:04:08
wählen das ich zufällig bestimmen das
00:04:10
wäre durch die zweite möglichkeit die
00:04:12
dritte möglichkeit wäre dass ich drei
00:04:14
werte zufällig bestimmen und davon an
00:04:17
den milderen benutze als trend ja das
00:04:21
war schon mal sehr viele informationen
00:04:22
vorab ich denk mal am klarsten wird es
00:04:25
wie immer mit einem konkreten beispiel
00:04:27
deswegen gehe ich jetzt mal aber an die
00:04:28
tafel macht ein beispiel und zeigt
00:04:31
schritt für schritt wie denn der krieg
00:04:33
sorg funktioniert und dann könnt ihr das
00:04:35
auch wirklich sukzessive nachverfolgen
00:04:37
wieder eigentlich arbeitet also bis
00:04:40
gleich
00:04:43
so ich gebe euch mal einen kurzen
00:04:45
überblick wir haben jetzt hier eine rey
00:04:48
mit acht werten und die sind nicht
00:04:51
sortiert und wir haben hier ganz links
00:04:56
in der obersten ecke den index stehen
00:04:59
und ganz rechts auf dem letzten element
00:05:01
den index j das heißt wir brauchen jetzt
00:05:04
für den quick sword 2
00:05:05
indizes einer fängt von vorne an der
00:05:09
andere fängt von vom hinteren ende aus
00:05:11
an wie genau zeige ich euch gleich jetzt
00:05:15
brauchen wir nämlich erstmal das pivot
00:05:16
element und der einfachheit halber
00:05:18
wählen wir jetzt das erste element als
00:05:21
pivot element und das erste element ist
00:05:24
die 14 und die tragen jetzt hier in
00:05:27
dieser spalte pivot ein also 14 das ist
00:05:31
unser pivot element so jetzt gibt es
00:05:34
hier noch zwei spalten für zahlen
00:05:36
tauschen dort tragen wir gleich die
00:05:38
beiden zahlen ein die im re die plätze
00:05:40
tauschen werden allerdings müssen wir
00:05:42
diese beiden zahlen jetzt erst mal
00:05:44
finden
00:05:45
und das geht folgendermaßen wir fangen
00:05:48
vorne an mit dem index der läuft jetzt
00:05:50
von links nach rechts und wir gehen die
00:05:53
einzelnen elemente durch und suchen
00:05:55
einen wert der größer gleich dem pivot
00:05:57
element ist das heißt wir haben jetzt
00:06:00
erstmal den wert 7 der ist nicht grösser
00:06:02
9 auch nicht aber die 20 und jetzt
00:06:06
machen wir mal hier sind kleinen punkt
00:06:07
rein damit ich weiß wo man index
00:06:10
momentan steht da steht jetzt hier auf
00:06:12
der 20 jetzt gehe ich ans hintere ende
00:06:15
und beginne mit dem index hat nach links
00:06:19
zu gehen und suche einen wert der
00:06:21
kleiner gleich den pv element ist die 19
00:06:24
ist nicht kleiner aber 11.11 es kleiner
00:06:27
als 14 dann mache ich mir auch einen
00:06:29
kleinen punkt rein damit ich weiß wo man
00:06:31
indexiert stehen geblieben ist so 20 und
00:06:35
11 müssen jetzt die plätze tauschen das
00:06:37
trage ich hier ein 20
00:06:40
und 11 und in der zeile darunter
00:06:43
schreibe ich jetzt die neue anordnung
00:06:46
des arrays 14
00:06:49
79 hier wurde jetzt getauscht also die
00:06:52
elf steht jetzt hier
00:06:57
16.8 hier landet jetzt die 20
00:07:01
und die 19 sowohl element bleibt gleich
00:07:05
das schreibe ich jetzt nicht jedes mal
00:07:06
neu hin jetzt müssen wir weiter suchen
00:07:09
und zwar genau an der stelle wo wir
00:07:11
stehen geblieben sind da habe ich mir
00:07:12
diesen punkt gemacht das heißt dort
00:07:15
steht man index und ich suche jetzt
00:07:17
weiter nach einem wert größer gleich
00:07:19
sechs gleich 14 dem pivot element und
00:07:22
das wäre hier schon sofort die 16 16 ist
00:07:25
größer gleich 14
00:07:27
jetzt habe ich den ersten treffer
00:07:29
gelandet dann gehe ich wieder zum index
00:07:32
j auf die rechte seite der steht ja hier
00:07:34
wo ich im punkt gesetzt habe und ich geh
00:07:37
jetzt ein zweiter nach links und suche
00:07:39
ein wert der kleiner gleich 14 ist und
00:07:41
die acht ist dann direkt der nächste
00:07:43
treffer
00:07:44
also hier habe ich wieder zwei werte die
00:07:46
die plätze tauschen müssen 16
00:07:50
und 8 tauschen die plätze
00:07:52
dann schreibe ich in die nächste zeile
00:07:54
wieder die neue anordnung hin 14 7 9 11
00:08:01
jetzt wird hier getauscht also
00:08:04
816 20 und 19
00:08:09
so mein index ii steht jetzt hier auf
00:08:13
der 16 auf der ehemaligen jetzt der acht
00:08:15
und indexiert steht hier auf der
00:08:18
ehemaligen acht jetzt 16 wie gehe ich
00:08:21
weiter vor ich muss wieder den index um
00:08:23
1 erhöhen das heißt es manchmal zwei
00:08:26
punkte hin index und j beide treffen
00:08:30
sich jetzt hier auf der 16 immer wenn
00:08:32
die beiden indizes sich treffen dann ist
00:08:35
das meiner abbruch bedingung für diesen
00:08:36
durchgang das heißt jetzt kann ich mein
00:08:39
niveau element positionieren und meine
00:08:42
race aufteilen ja was ist jetzt zu tun
00:08:46
ich tausche jetzt das pivot element an
00:08:49
die position - 1 ich stehe hier auf der
00:08:53
16 - 1 wäre also da oder mit anderen
00:08:56
worten ich tausche das pivot element mit
00:08:59
dem letzten element das nicht größer ist
00:09:01
als es selbst also 14 und 8 tauschen
00:09:05
jetzt hier die plätze
00:09:09
also die acht landet jetzt ganz vorne
00:09:14
79
00:09:17
11 hier landet das pivot element14
00:09:22
16
00:09:25
20.06 sein
00:09:27
und 19 so jetzt ist das pivot element an
00:09:33
der richtigen stelle deswegen mache ich
00:09:35
mal hier so eine kleine umrandung dahin
00:09:40
damit klar ist die 14 ist fertig
00:09:44
sortiert das heißt da wird werde ich
00:09:47
nicht mehr daran gehen die bleibt da
00:09:49
stehen bis zum ende
00:09:50
jetzt habe ich zwei teile riss
00:09:52
produziert links stehen alle werte die
00:09:55
kleiner sind als das parlament rechts in
00:09:58
dem teile riss den alle werte die größer
00:10:00
sind in sich sind die aber noch nicht
00:10:02
sortiert so wie geht es jetzt weiter ich
00:10:06
nehme jetzt die teile race und gehe
00:10:08
genauso vor wie gerade am anfang auch
00:10:11
also das neue teile hier wäre ja 87 9
00:10:17
11 und hier bestimme ich jetzt auch
00:10:20
wieder das niveau element und das ist
00:10:22
immer das erste habe ich ja gesagt also
00:10:24
wenn man jetzt hier in die spalte pivot
00:10:26
die acht reinschreiben das ist mein
00:10:28
neues pivot element ja und jetzt gehe
00:10:31
ich wieder genauso vor wie gerade auch
00:10:32
mit dem index ivan da ich nach rechts
00:10:35
und suche ein wert der größer gleich
00:10:37
acht ist und dann finde ich hier die
00:10:39
neun
00:10:40
so mein index j steht er jetzt hier auf
00:10:43
der 11 und nicht wandern nach links um
00:10:46
suche einen wert der kleiner gleich acht
00:10:48
ist die elf passt nicht und auf der neun
00:10:52
sitze ich schon mit meinem index das
00:10:55
heißt hier habe ich dann wieder die
00:10:56
abbruch bedingung die union treffen sich
00:10:59
also muss ich das pico element wieder an
00:11:02
die richtige position wechseln nämlich
00:11:04
an die position ii - 1 wie steht hier
00:11:08
auf der 9
00:11:09
das heißt 8 und 7 tauschen die plätze
00:11:16
8 und 7 dann schreiben wir die neue
00:11:20
zeile hin sieben acht neun und
00:11:25
elf und das pro element kann ich jetzt
00:11:28
wieder markieren das ist sortiert also
00:11:32
macht man kästchen drum
00:11:35
so jetzt habe ich wieder zwei teile riss
00:11:38
produziert einmaleins was ein element
00:11:41
ist mit der 7 und weil das ein element
00:11:43
ist kann ich auch direkt ein kästchen
00:11:45
drum machen
00:11:46
denn da kann ja nichts weiter passieren
00:11:49
der ist jetzt auch sortiert und auf der
00:11:52
rechten seite haben wir die neuen und
00:11:54
die elf das wäre jetzt das neue teil wo
00:11:58
ich auch wieder das niveau element
00:12:00
bestimmen muss hier wäre das erste
00:12:02
element an die 9
00:12:04
also neu ist dass pro element und jetzt
00:12:08
gilt wieder genauso vor wie vorhin auch
00:12:10
ich suche mit dem index nach einem wert
00:12:14
der größer gleich dem pivot element ist
00:12:17
das heißt ich lande hier auf der 11 habt
00:12:19
dann treffer da sitzt aber auch schon
00:12:21
mein index j das heißt ich habe jetzt
00:12:23
auch sofort die abbruch bedingung also
00:12:25
muss ich mein niveau element an die
00:12:27
position - eins tauschen und das wäre
00:12:31
dann die position links von der 11 da
00:12:33
steht die neuen sowieso schon also im
00:12:36
prinzip tauscht die neuen mit der neuen
00:12:37
dem platz bleibt also da stehen wo sie
00:12:40
ist und somit wäre die neuen sortiert
00:12:46
und weil wir jetzt einen teil ihrer
00:12:50
größe 1 bekommen mit der elf kann ich
00:12:52
hier auch direkt ein kästchen drum
00:12:54
zeichnen das ist dann auch sortiert
00:12:58
so jetzt haben wir aber noch das erste
00:13:01
teil von hier oben noch zu sortieren
00:13:04
also 16
00:13:06
[Musik]
00:13:08
20 19 das erste element wird meint ivo
00:13:14
16 jetzt suche ich wieder von links
00:13:17
kommend mit im index je nach einem wert
00:13:20
der größer gleich 16 ist und finde hier
00:13:22
ein mit der 20 jetzt muss ich mit
00:13:25
indexiert von rechts nach links wandern
00:13:27
und einen wert suchen der kleiner gleich
00:13:29
16 ist die 19 stimmt nicht 20 jetzt habe
00:13:34
ich hier wieder meine abbruch bedingung
00:13:36
da sitzt ja schon der index also was
00:13:39
passiert ich tausche mein pivot element
00:13:42
an die position ii - 1 - 1 wäre also
00:13:46
links von der 20 die 16 tauscht mit der
00:13:49
16
00:13:50
mit anderen worten die 16 bleibt da
00:13:52
stehen wo sie ist und kann als sortiert
00:13:54
markiert werden also kästchen darum
00:14:02
was bleibt übrig das rechte teil mit 20
00:14:07
und 19 pivot element wie immer das erste
00:14:10
element 20 jetzt suche ich wieder nach
00:14:14
einem wert der größer gleich 20 ist ich
00:14:17
wandere mit index nach rechts und lande
00:14:21
hier am ende ohne einen wert gefunden zu
00:14:24
haben der größer gleich 20 ist in dem
00:14:27
fall muss das pivot element das größte
00:14:30
element sein und muss damit ans ende
00:14:33
gewechselt werden also 20 und 19
00:14:37
tauschen die plätze
00:14:41
dann kann ich die 20 markieren als
00:14:45
sortiert
00:14:49
und weil die 19 jetzt alleine dasteht
00:14:52
kann nichts spannendes mehr passieren
00:14:54
die ist dann auch als sortiert zu
00:14:56
markieren
00:15:00
und wenn man jetzt von links nach rechts
00:15:02
die umrandeten kästchen least haben wir
00:15:04
eine aufsteigende sortierung also
00:15:08
789 11 14 16 19 20
00:15:17
so jetzt zeige ich euch noch mal ein
00:15:19
anderes beispiel nehme ich ja ein
00:15:22
negativbeispiel für den quick sword wenn
00:15:24
er nämlich ein bereits sortiertes array
00:15:26
sortieren soll wer immer das erste
00:15:28
element als pivot element bestimmen dann
00:15:31
bekommen wir nämlich eine schlechte eine
00:15:33
ungünstige aufteilung und letztendlich
00:15:35
quadratische laufzeit also wir machen
00:15:38
die gleiche strategie wie gerade auch
00:15:40
und wählen jetzt hier das erste element
00:15:42
also die zwei als pivot element so jetzt
00:15:46
suche ich einen wert der größer ist als
00:15:49
die zwei und finde hier sofort mit der
00:15:52
vier einen passenden wert somit index j
00:15:54
muss ich jetzt von rechts nach links
00:15:56
wandern einen wert suchen der kleiner
00:15:58
gleich dem pivot ist und dort werde ich
00:16:01
überhaupt nicht fündig ich laufe immer
00:16:03
weiter immer weiter nach links bis ich
00:16:05
hier auf der vier lande wo man index eh
00:16:07
schon positioniert ist also abbruch
00:16:10
bedingung die zwei wird an die position
00:16:12
ii - 1 getauscht also bleibt
00:16:15
letztendlich da stehen wo sie ist und
00:16:17
ich kann jetzt die zwei als sortiert
00:16:21
markieren
00:16:23
und jetzt sieht man die ungünstige
00:16:25
aufteilung
00:16:27
ich habe letztendlich links von der 2
00:16:30
überhaupt kein teile rey und der
00:16:33
komplette rest ist auf der rechten seite
00:16:35
von mr ich habe also eine äußerst
00:16:38
ungünstige aufteilung und müsste jetzt
00:16:40
hier mit
00:16:41
diesem teil re weitermachen 4 6 8 10
00:16:48
12 14
00:16:51
16 pivot element
00:16:54
erstes element die vier auch hier wieder
00:16:57
suche ich von links ein wert der größer
00:17:00
gleich vier ist habe ich hier mit der
00:17:02
sechs gefunden und von rechts komme ich
00:17:04
wieder mit index j finde keinen wert der
00:17:07
kleiner gleich vier ist lande auf der
00:17:09
sechs wo auch index schon ist und dann
00:17:12
muss ich die vier an die position ii - 1
00:17:16
tauschen also i die vier bleibt stehen
00:17:19
wo sie ist
00:17:21
und dann kann ich die vier als markiert
00:17:24
sortieren
00:17:27
und so weiter ich glaube ihr könnt sehen
00:17:30
wie sich das entwickelt
00:17:31
das heißt es wird immer nur vorne die
00:17:33
erste zahl
00:17:35
abgeschnitten und man produziert
00:17:38
letztendlich ein einzelnes neues teile
00:17:41
rey mit dem kompletten rest des arrays
00:17:44
und das führt letztendlich zu einer
00:17:47
quadratischen laufzeit
00:17:49
ja das wäre also ein grund dafür dass
00:17:52
pivot element nicht so zu wählen wie ich
00:17:54
euch das gezeigt habe immer das erste
00:17:56
element sondern den zufall entscheiden
00:17:59
zu lassen denn dann kann ich davon
00:18:01
ausgehen oder darf ich davon ausgehen
00:18:03
dass ich eine linear logarithmische
00:18:05
laufzeit bekomme also eine komplexität
00:18:08
von o von n mal lockt von in
00:18:11
so hier seht ihr noch mal diese
00:18:13
ungünstige oder schlechte zerlegung wenn
00:18:16
das re bereits sortiert ist so bekomme
00:18:20
ich halt eine quadratische laufzeit also
00:18:22
meine raider größe m wird immer
00:18:24
aufgeteilt in der form nach links kommt
00:18:27
ein element und -1 elemente kommen dann
00:18:31
auf die rechte seite und so weiter und
00:18:33
so kriegen wir halt diesen ungünstigen
00:18:35
fall mit opa nennt quadrat also
00:18:37
quadratischer laufzeit
00:18:40
hier auf diesem bild seht ihr den besten
00:18:43
fall nämlich immer dann wenn mein pivot
00:18:45
element genau in der mitte landet und
00:18:48
meine rey in zwei gleich große teile
00:18:50
race aufteilt so kriege ich eine
00:18:52
logarithmische tiefe und letztendlich
00:18:54
ein lineal logarithmische laufzeit also
00:18:57
von n loco nennen
00:19:00
auf dieser folie seht ihr mal drei
00:19:04
unterschiedliche konstellationen vom
00:19:06
quick sox nämlich mit beispiel die
00:19:09
optimale aufteilung dann wenn das pivot
00:19:12
element immer genau in der mitte landet
00:19:14
da kriegen wir halt die linear
00:19:16
logarithmische laufzeit beispiel cs dann
00:19:19
genau das negative gegenbeispiel mit
00:19:21
einer mit einem sortierten re wo ich
00:19:23
dann immer die aufteilung 1 zu ende -1
00:19:27
bekomme und das resultiert dann
00:19:30
schließlich in quadratischer laufzeit
00:19:32
und links unten mit beispiel b sehen wir
00:19:35
ja die aufteilung wie sie im mittel zu
00:19:38
erwarten ist
00:19:43
ja das ist der king saud gewesen ich
00:19:47
hoffe ich konnte euch den fix von
00:19:48
halbwegs verständlich vermitteln und
00:19:51
wenn er interesse noch an anderen
00:19:52
tiergruppen habt ich habe noch einige
00:19:54
andere videos produzieren mit zum
00:19:57
beispiel dem higgs ort oder dem counting
00:20:00
sword könnte das in meinen anderen
00:20:01
videos natürlich finden ich freue mich
00:20:04
meinen daumen hoch und sagte zum
00:20:05
nächsten mal
