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. Ș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?