>> MARK GROZEN-SMITH: Bună, eu sunt Mark Grozen-Smith, iar acest lucru este Quicksort.
La fel ca un fel de introducere și bule fel, Quicksort este un algoritm pentru
sortare o listă sau o serie de lucruri.
Pentru simplitate, să presupunem că cei lucrurile sunt doar numere întregi, dar
Știu că Quicksort funcționează pentru mai mult decât numere.
QuickStart este un pic mai complicat de inserare sau cu bule, dar e
de asemenea, mult mai eficient în cele mai multe cazuri.
Așteaptă o secundă.
A spune doar "cel mai cazuri, "nu" tot "?
Interesant, nr.
Nu toate cazurile sunt la fel.
Nu vă faceți griji cu privire la acest detaliu, dacă nu s-au văzut notație mare O încă, dar
Quicksort este un O (n pătrat) algoritm cel mai rău caz, la fel ca
inserare sau bule de sortare.
Cu toate acestea, ea acționează de obicei mult mai ca un m algoritm analog vechi.
De ce?
Vom reveni la asta mai târziu.
Dar de acum, hai să învățăm cum funcționează Quicksort.
>> Deci, haideți să mergem prin Quicksorting acest matrice de numere întregi de la cel mai mic
la cel mai mare.
Aici avem numerele întregi 6, 5, 1, 3, 8, 4, 7, 9, și 2.
În primul rând, ne-am alege elementul final de această matrice - în acest caz, doi -
și de apel ca "pivot". Apoi, ne-am începe să se uite la două lucruri -
unul, cel mai scazut indice, pe care voi referi pentru ca stau la dreapta
perete, și, doi, cel mai din stânga elemente, pe care le voi numi "curent
Element. "Ceea ce vom face este uite toate celelalte elemente, altele
decât pivotul, și a pus toate elementele mai mic decât pivotul la
rămas din perete și toți cei mai mare decât pivotul la
dreaptă a peretelui.
Apoi, în cele din urmă, vom renunța la pivotul chiar pe perete să-l pună între
toate numerele mai mici decât și toate numerele mai mari.
>> Deci, haideți să facem asta.
Pick up 2, a pus pe peretele de la început, și sunați la 6 "curent
Element. "Așa că vrem să se uite la elementul nostru curent, 6.
Și, din moment ce este mai mare decât 2, l-am lăsa acolo la
dreaptă a peretelui.
Apoi, vom trece la a privi la 5 ca noastre element de curent și să vedem că această
este, din nou, mai mare decât pivotul, deci lăsați-l în cazul în care este pe dreapta
parte a peretelui.
Noi mergem mai departe.
Elementul nostru actual este acum 1, si - oh.
Acest lucru este diferit acum.
Elementul curent este acum mai mică decât pivot, așa că vrem să-l puneți
în partea stângă a peretelui.
Pentru a face acest lucru, hai să porniți Element curent cu cel mai mic indice
stând doar la dreptul de perete.
Acum, vom trece zidul sus cu un index deci o este pe stânga
parte a peretelui acum.
>> Așteaptă.
Am amestecat elementele din partea dreapta a peretelui, nu-i așa?
Nu vă faceți griji.
Asta e bine.
Singurul lucru de care ne pasă de acum este că toate aceste elemente pentru a
dreaptă a peretelui sunt mai mari decât pivotul.
Nici un ordin real se presupune încă.
>> Acum, înapoi la sortare.
Deci, vom continua pe uita la restul elementelor.
Și în acest caz, vom vedea că există există alte elemente mai puțin decât
pivot, așa că le lăsa pe în partea dreaptă a peretelui.
În cele din urmă, ajungem la elementul curent și a vedea că acesta este pivotul.
Acum, ceea ce înseamnă că avem două secțiuni ale matrice, prima fiind
mic pe pivotul și în partea stângă a peretelui, iar a doua fiind
mai mare decât pivotul la partea dreaptă a peretelui.
Vrem să pună elementul pivot între cei doi, iar apoi vom ști
că pivotul este în dreptul său loc sortat finală.
Deci, vom trece primul element pe partea dreaptă a peretelui cu pivotul,
și știm că pivotul de în poziția sa potrivit.
>> Atunci vom repeta acest proces pentru subarrays stânga și la dreapta a pivotului.
De la ultima subarray este doar una , de mult timp, știm că e deja
sortat, deoarece cum poți fi de comanda daca esti doar un element?
Pentru partea dreaptă a subarray, am vedea că pivotul este 5, iar peretele
este plecat doar de 6.
Și elementul curent, de asemenea, începe ca 6.
Deci 6 este mai mare de 5.
Lăsăm în care se află pe partea dreaptă a peretelui.
Acum, se deplasează pe, 3 este mai mică de 5.
Deci, l-am schimba cu primul element doar dreptul peretelui.
Acum, m-am mutat pe perete la unul.
Acum, de a trece la 8.
8 este mai mare de 5, și așa am pleca.
4 este mai mică de 5, așa că l-am schimba.
Și pe.
>> De fiecare dată când repetați procesul privind laturile stânga și dreapta de matrice. noi
alege un pivot și de a face comparațiile și de a crea un alt nivel de stânga și
subarrays dreapta.
Acest apel recursiv va continua până vom ajunge la sfârșitul atunci când ne-am
împărțit matrice de ansamblu în doar subarrays de lungime 1.
De acolo, știm că matricea este sortat pentru că fiecare element are, la
un moment dat, a fost un pivot.
Cu alte cuvinte, pentru fiecare element, toate numerele de la stânga sunt mai puțin
valorile și toate numerele de au dreptul de valori mai mari.
>> Această metodă funcționează foarte bine în cazul în care valoare a pivotului este aleasă
aproximativ la mijlocul Gama de valori lista.
Acest lucru ar însemna că, după ce ne-am muta elemente, în jurul valorii de acolo despre cât mai multe
elemente la stânga pivotului cum există la dreapta.
Și natura divide et impera a Algoritm Quicksort este apoi luate
profita din plin de.
Acest lucru creează o execuție de O (n log n,) n pentru că avem de-a face n minus 1
comparații cu privire la fiecare generație și jurnal n pentru că trebuie să împartă lista
log n ori.
Cu toate acestea, în cele mai rele cazuri, această algoritm poate fi de fapt, O (n
pătrat.) Să presupunem că la fiecare generație, pivotul doar așa se întâmplă să fie
mai mică sau cea mai mare a Numerele suntem de sortare.
Acest lucru ar însemna de rupere jos lista de n ori și de luare n minus 1
comparații fiecare dată.
Astfel, o a n pătrat.
>> Cum putem îmbunătăți metoda?
O modalitate buna de a îmbunătăți metoda este pentru a reduce cu privire la probabilitatea ca
runtime este vreodată de fapt o de n pătrat.
Amintiți-vă acest lucru cel mai rău, cel mai rău caz se poate întâmpla doar atunci când
pivot ales este întotdeauna cea mai mare sau cea mai mică valoare în matrice.
Pentru a asigura acest lucru este mai puțin probabil să se întâmple, putem gasi pivotul de
alegerea elemente multiple și luând valoarea medie.
>> Numele meu este Mark Grozen-Smith, și acest lucru este CS50.
>> Pentru simplitate, să presupunem că cei lucrurile sunt doar numere întregi, dar
Știu că QUICKSERT -
QUICKSERT?
Scuze.
>> Aici avem numerele întregi 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Serios?
>> SPEAKER 2: Nu te opri aici.
>> SPEAKER 1: Serios?