>> MARCA GROZEN-SMITH: Hola, sóc Marc Grozen-Smith, i aquesta és l'ordenació ràpida.
Igual que l'ordenació per inserció i la bombolla espècie, l'ordenació ràpida és un algorisme per
ordenar una llista o una matriu de coses.
Per simplificar, suposarem que els les coses són només nombres enters, però
sabem que treballa per a l'ordenació ràpida més enllà dels números.
Inici ràpid és una mica més complicat d'inserció o de bombolles, però és
també molt més eficient en la majoria dels casos.
Espera un segon.
¿Va dir "més casos ", no" tots "?
Curiosament, cap.
No tots els casos són la mateixa.
No et preocupis per aquest detall si no han vist la notació O gran encara, però
Ordenació ràpida és una operació O (n al quadrat) algorisme en el pitjor, igual que
inserció o espècie de bombolla.
No obstant això, en general actua molt més com un vell m algorisme analògic.
Per què?
Ens posarem en contacte amb això més tard.
Però per ara, anem a aprendre com funciona l'ordenació ràpida.
>> Així que anem a caminar a través d'aquest Quicksorting matriu d'enters de menys
a més gran.
Aquí tenim els enters 6, 5, 1, 3, 8, 4, 7, 9, i 2.
En primer lloc, vam triar l'element final de aquesta matriu - en aquest cas, dos -
i cridar a que el "pivot". A continuació, es començar a tenir en compte dues coses -
un, l'índex més baix, el que em referiré a com mantenir-se a la dreta del
la paret, i, dos, el més a l'esquerra element, que vaig a cridar a la "corrent
element. "El que farem és buscar tots els altres elements, altres
que el pivot, i posar tots els elements més petit que el pivot per a la
esquerra de la paret i tots aquells més gran que el pivot per a la
dret de la paret.
Llavors, finalment, ens deixarem caure el pivot just en aquesta paret per posar entre
tots els números més petits del que i tots els números més grans.
>> Així que anem a fer això.
Llevant el 2, posar la paret a la començant, i truqui al 6 la "corrent
element ". Així que volem veure nostre element actual, el 6.
I ja que és més gran que el 2, el deixem aquí per a la
dret de la paret.
A continuació, passem a mirar el 5 com el nostre element actual i veure que aquesta
és, de nou, més gran que el de pivot, per la qual cosa deixar-lo on està a la dreta
costat de la paret.
Seguim endavant.
El nostre element actual és ara 1, i - oh.
Això és diferent ara.
L'element actual és ara menor que el pivot, pel que volem posar
a l'esquerra de la paret.
Per a això, canviarem la element actual amb l'índex més baix
assegut just a la dreta de la paret.
Ara, passem la paret fins a un índex de manera que el 1 és a l'esquerra
costat de la paret ara.
>> Esperi.
Acabo confós els elements de la costat dret de la paret, no?
No es preocupi.
Això està bé.
L'únic que ens importa per ara és que tots aquests elements a la
dret de la paret són més grans que el pivot.
No hi ha comanda actual s'assumeix encara.
>> Ara, de tornada a la classificació.
Així que continuem mirant la resta dels elements.
I en aquest cas, veiem que hi ha no hi ha altres elements menys que el
pivot, així que els deixem en tot la part dreta de la paret.
Finalment, arribem a l'element actual i veure que és el pivot.
Ara, això vol dir que tenim dos seccions de la matriu, el primer ésser
petita al pivot i al costat esquerre de la paret, i el segon ser
més gran que el pivot per a la costat dret de la paret.
Volem posar l'element de pivot entre els dos, i llavors sabrem
que el pivot té tot el dret lloc classificat final.
Així que canviem el primer element de la costat dret de la paret amb el pivot,
i sabem del pivot en la seva posició correcta.
>> Després es repeteix aquest procés per al subarrays esquerra i dreta del pivot.
Des de l'última submatriu és només una element llarg, sabem que això és ja
ordenada, perquè com es pot estar fora de ordenar si vostè és només un element?
Pel costat dret de la submatriu, ens veure que el pivot és 5, i el mur
està just a l'esquerra de la 6.
I l'element actual també que comença com el 6.
Així que 6 és més gran que 5.
Ho deixem on està en el costat dret de la paret.
Ara, passant, 3 és menor que 5.
Així que canviem amb el primer element tot just a la dreta de la paret.
Ara, em vaig mudar de la paret fins a una.
Ara, passant a la 8.
8 és més gran que 5, i així ho vam deixar.
La figura 4 és menor que 5, de manera que canviar ell.
I en.
>> Cada vegada que repetim el procés en el costats esquerre i dret de la matriu. nosaltres
triar un pivot i fer les comparacions i crear un altre nivell de l'esquerra i
subarrays dreta.
Aquesta crida recursiva continuarà fins arribem al final quan hem
dividit la matriu global en només subconjunts de longitud 1.
A partir d'aquí, sabem que la matriu s'ordena ja que cada element té,
algun moment, ha estat un pivot.
En altres paraules, per a cada element, tot els números a l'esquerra són menors
valors i tots els números a la dret tenen majors valors.
>> Aquest mètode funciona molt bé si el valor del pivot triat és
aproximadament en el centre rang dels valors de la llista.
Això significaria que, després que ens movem elements voltant, hi ha gairebé tants
elements a l'esquerra del pivot ja que hi ha a la dreta.
I la naturalesa de divideix i venceràs de l' Després es pren l'algorisme quicksort
tot el profit a.
Això crea un temps d'execució d'O (n log n,) el n perquè hem de fer n almenys 1
comparacions en cada generació i registre n perquè hem de dividir la llista
log n vegades.
No obstant això, en el pitjor dels casos, aquest algorisme en realitat pot ser O (n
al quadrat.) Suposem que en cada generació, el pivot que passa a ser el
més petit o el més gran de la nombres que estem de classificació.
Això significaria trencar la llista n vegades i la presa de N almenys 1
comparacions cada vegada.
Per tant, o de n al quadrat.
>> Com podem millorar el mètode?
Una bona manera de millorar el mètode és per reduir la probabilitat que
el temps d'execució és sempre realment O de n al quadrat.
Recordi que aquesta pitjor, pitjor dels casos només pot ocórrer quan la
pivot triat és sempre el més alt o el valor més baix en la matriu.
Per garantir que això és menys probable que passi, podem trobar el pivot per
l'elecció de múltiples elements i tenint el valor de la mitjana.
>> El meu nom és Mark Grozen-Smith, i això és CS50.
>> Per simplificar, suposarem que els les coses són només nombres enters, però
saber que QUICKSERT -
QUICKSERT?
Ho sento.
>> Aquí tenim els enters 6, 5, 1, 3, 8, 4, 9.
>> ALTAVEU 1: De debò?
>> ALTAVEU 2: No s'atura allà.
>> ALTAVEU 1: De debò?