>> MARK GROZEN-SMITH: Hoi, ik ben Mark Grozen-Smith, en dit is Quicksort.
Net als insertion sort en bubble sorteren, Quicksort is een algoritme voor het
sorteren van een lijst of een reeks van dingen.
Voor de eenvoud, laten we aannemen dat die dingen zijn gewoon integers, maar
weten dat Quicksort werkt voor meer dan getallen.
Snelstart is een beetje ingewikkelder dan inbrengen of bubble, maar het is
ook veel efficiënter in de meeste gevallen.
Wacht even.
Zei hij net "meest gevallen ", niet" alle "?
Interessant, nee.
Niet alle gevallen dezelfde.
Maak je geen zorgen over dit detail als u hebben grote O notatie nog niet gezien, maar
Quicksort is een O (n kwadraat) algoritme in het slechtste geval, net als
insertie of bubble sort.
Toch treedt meestal veel meer als een oude analoge m algoritme.
Waarom?
We komen terug om dat later te krijgen.
Maar voor nu, laten we gewoon leren hoe Quicksort werkt.
>> Dus laten we lopen door Quicksorting deze array van integers van klein
naar de grootste.
Hier hebben we de getallen 6, 5, 1, 3, 8, 4, 7, 9, en 2.
Ten eerste, we halen het sluitstuk van deze array - in dit geval twee -
en noemen dat de "spil." Vervolgens hebben we beginnen te kijken naar twee dingen -
een, de laagste index, die ik zal verwijzen als altijd rechts van
de muur, en, twee, de meest linkse element, dat ik de "huidige bel
element. "Wat we gaan doen is kijk alle andere elementen, andere
dan de spil, en zet alle elementen kleiner dan de spil aan de
links van de muur en al die groter dan de spil aan de
rechts van de muur.
En dan, eindelijk, we zullen de spil te laten vallen recht op die muur te zetten tussen
alle getallen kleiner dan en alle getallen groter.
>> Dus laten we dat doen.
Pak de 2, zet de muur aan de begin, en bel de 6 de "huidige
element. "Zo willen we kijken naar onze huidige element, de 6.
En omdat het groter is dan de 2, laten we het daar op de
rechts van de muur.
Daarna gaan we verder kijken naar de 5 als onze huidige element en zie dat deze
is wederom groter dan de spil, dus laten wanneer het op de juiste
zijde van de wand.
We gaan verder.
Onze huidige element is nu 1, en - oh.
Dit is nu anders.
De huidige element is nu kleiner dan de spil, dus we willen het te zetten
links van de wand.
Om dit te doen, laten we gewoon schakelen de huidige element met de laagste index
zitten net aan de rechterkant van de muur.
Nu gaan we de muur op een index dus de 1 is links
zijde van de wand nu.
>> Wacht.
Ik gemengd de elementen op de rechterkant van de muur, niet ik?
Maak je geen zorgen.
Dat is prima.
Het enige wat we de zorg over voor nu is dat al deze elementen in de
rechts van de muur zijn groter dan de spil.
Geen werkelijke volgorde is nog verondersteld.
>> Nu, terug naar het sorteren.
Dus gaan we op zoek naar de rest van de elementen.
En in dit geval, zien we dat er geen andere elementen dan de
pivot, dus laten we ze allemaal op rechts van de muur.
Tot slot komen we bij de huidige element en zie dat het is de spil.
Nu, dat betekent dat we twee secties van de array, waarvan de eerste
klein op de spil en aan de linkerkant van de muur, en de tweede is
groter dan de spil aan de rechts van de muur.
We willen de pivot element tussen gezet de twee, en dan zullen we weten
dat de spil is in haar recht laatste gesorteerde plaats.
Dus schakelen we dat element de rechts van de muur met de spil,
en we weten dat de spil van in zijn juiste positie.
>> We herhaal dit proces voor de subarrays links en rechts van het scharnier.
Sinds de laatste subarray is slechts een element lang, weten we dat er al
gesorteerde want hoe kun je uit bestellen als je slechts een element bent?
Voor de rechterkant van de subarray, we zien dat de spil is 5, en de muur
is net links van de 6.
En het huidige element ook begint als de 6.
Dus 6 groter is dan 5.
We laten wanneer het op de rechts van de muur.
Nu, het bewegen, 3 minder dan 5.
Dus schakelen we het met het eerste element net rechts van de muur.
Nu, ik bewoog de muur boven een.
Nu, over te gaan tot de 8.
8 groter is dan 5, en zo laten we het.
De 4 is minder dan 5, dus we wisselen het.
En op.
>> Elke keer dat we herhaal het proces op de linker-en rechterzijde van de array. we
kiezen voor een draaipunt en doe de vergelijkingen en een andere mate van linker en
rechts subarrays.
Deze recursieve aanroep zal doorgaan tot we het einde toen we hebben bereikt
verdeelden de totale array naar net subarrays van lengte 1.
Vanaf daar, we kennen de array wordt gesorteerd omdat elk element heeft, op
een bepaald punt, is een spil.
Met andere woorden, voor elk element, alle de getallen aan de linkerkant zijn minder
waarden en alle nummers op de recht hebben hogere waarden.
>> Deze methode werkt goed als de waarde van de gekozen spil is
ongeveer in het midden bereik van de lijst waarden.
Dit zou betekenen dat, nadat we verhuizen elementen rond, er ongeveer evenveel
elementen links van de spil aangezien er naar rechts.
En de verdeel-en-heers aard van de Quicksort algoritme wordt vervolgens
volle te profiteren van.
Dit creëert een looptijd van O (n log n,) de n omdat we moeten doen n minus 1
vergelijkingen op elke generatie en log n want we moeten de lijst te verdelen
log n keer.
In de ergste gevallen algoritme kan eigenlijk O (n
kwadraat.) Stel voor elke generatie, de spil gewoon zo gebeurt te zijn de
kleinste of de grootste van de nummers we sorteren.
Dit zou betekenen het afbreken van de lijst n keer en het maken n minus 1
vergelijkingen elke keer weer.
Aldus o n kwadraat.
>> Hoe kunnen we de methode?
Een goede manier om de werkwijze te verbeteren is om te bezuinigen op de kans dat
de runtime is eigenlijk ooit o van n kwadraat.
Onthoud dit ergste, worst case scenario kan alleen gebeuren wanneer de
pivot gekozen is altijd de hoogste of kleinste waarde in de array.
Om dit minder waarschijnlijk gebeuren, kunnen we de pivot vinden door
kiezen meerdere elementen en het nemen van de mediane waarde.
>> Mijn naam is Mark Grozen-Smith, en dit is CS50.
>> Voor de eenvoud, laten we aannemen dat die dingen zijn gewoon integers, maar
weten dat Quicksert -
Quicksert?
Sorry.
>> Hier hebben we de gehele getallen 6, 5, 1, 3, 8, 4, 9.
>> LUIDSPREKER 1: Echt waar?
>> SPEAKER 2: Laat je daar niet stoppen.
>> LUIDSPREKER 1: Echt waar?