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