Quicksort Algorithmus / Quick Sort Sortierverfahren mit Beispiel (deutsch)
Studyflix
https://www.youtube.com/watch?v=eNUM23f6g-s

Transkript (automatisch erstellt)

0:00 du fragst dich wie der creeks ort funktioniert und benötigt zusätzlich auch noch infos zur laufzeit dann ist dieses video genau das richtige für dich
0:09 du willst ganz viele kostenlose videos zu java dann kommen auf star die flex de beim quiz ort handelt es sich um einen rekurs
0:18 even nicht stabilen sortier algorithmus der in verschiedenen varianten existiert auch die verwendete programmiersprache kann das genaue vorgehen des verfahrens
0:27 beeinflussen grundsätzlich gehört der krx ort aber zu den algorithmen die sich dass teile und herrsche prinzip zunutze machen
0:35 das zu sortieren der ey wird also solange kursiv zerlegt bis es sortiert ist wie genau der krx ort im allgemeinen vor geht schauen wir uns am besten an
0:44 einem beispiel an dafür wollen wir diese liste sortieren zuerst müssen wir ein pivot element aus der liste wählen
0:53 grundsätzlich kann das die jedes element sein zum beispiel das erste oder das letzte für eine optimale revision wird jedoch fast immer der median verwendet
1:03 wenn du eine bestimmte variante des quick sorg betrachters solltest du hier immer genau überprüfen wie das pivot element definiert ist unser quiz ort
1:12 soll der einfachheit halber das erste element wählen also die 6 diese setzen wir in die mitte des arrays und markieren das grün
1:21 die restlichen zahlen müssen wir nun entsprechend unseres pivot elements einsortieren alle zahlen die kleiner sind kommen auf die linke seite der
1:29 sechs und alle die größer sind auf die rechte seite die acht und die neuen wandern also nach rechts die 1 3 und 4 nach links
1:38 wie du siehst bleibt die ursprüngliche reihenfolge der anderen zahlen zu einander gleich wenn wir damit fertig sind steht das pivot element also an der
1:46 richtigen stelle auch alle anderen elemente stehen im vergleich zum pivot element auf der richtigen seite damit haben wir den ersten durchlauf geschafft
1:56 im zweiten durchlauf wählen wir wieder das erste element diesmal jedoch zwei die zwei für die linke hälfte und die acht für die rechte hälfte beide hälften
2:06 werden dann nach demselben prinzip wie dem der ersten runde geordnet wir setzen die beiden neuen pivot elemente in die mitte und sortieren den rest der hälfte
2:15 nach links und rechts im dritten durchgang willen wir dann entsprechend schon vier pivot elemente die einst die fünf die sieben und die 9
2:24 wir sehen sofort dass nur noch die fünf ein rest fällt hat das sortiert werden muss die anderen stehen für sich allein und damit bereits auf dem richtigen
2:32 platz wir wählen im vierten durchgang die drei als pivot element und sortieren die 4 1 sie steht schon auf dem richtigen platz
2:41 im letzten durchgang wählen wir dann die vier die als einzige übrig bleibt und sind fertig zum schluss müssen wir alle einzelnen elemente entsprechend ihrer
2:51 neuen anordnung verknüpfen und haben unsere fertig sortierte liste soweit also zum prinzip des kriegs ort der algorithmus lässt sich auch als in
3:01 place variante umsetzen dafür benötigt man noch zwei zusätzliche felder wie genau du das machst zeigen wir dir in unserem video clips ort
3:09 beispiel an vielen unis wirst du dieser version sogar häufig begegnen in jedem fall solltest du hier genau darauf achten welchen tricks orte in
3:19 deiner klausur bearbeiten sollst zum abschluss wollen wir uns noch mit der laufzeit beschäftigen wie der name schon andeutet haben wir es beim quick
3:29 sword mit einem sehr schnellen algorithmus zu tun im average case also im durchschnitt für den opernball logarithmisch von n
3:36 vergleiche aus im worst case dagegen beträgt die zeit komplexität von n hoch zwei das wäre beispielsweise der fall wenn das pivot element immer das letzte
3:46 element ist und die liste eigentlich schon sortiert ist dabei würden die teil listen immer nur um eins kleiner werden in der praxis kommt so etwas aber
3:56 ziemlich selten vor im best case die laufzeit genau wie im durchschnitt fall in dem fall wählt man das pro element so dass die teil ist
4:05 stets möglich gleich groß sind daher wird wie eingangs bereits erwähnt meistens der median als pivot element gewählt aufgrund seiner komplexität
4:15 gehört der quick sword in der praxis tatsächlich zu den beliebtesten sortier algorithmen er ist schnell und falls uns region zur verfügung steht auch ziemlich
4:24 einfach zu implementieren sehr gut jetzt solltest du einen guten einblick in die eigenschaften und das grundprinzip eines kriegs ort haben
4:33 der hat das video gefallen noch mehr kostenlose videos gibt's auch study flex de