MARK GROZEN-SMITH: Ciao, sono Marco Grozen-Smith, e questo è Quicksort. Proprio come insertion sort e bubble ordinamento, Quicksort è un algoritmo per l'ordinamento di un elenco o una serie di cose. Per semplicità, supponiamo che i le cose sono solo numeri interi, ma sa che Quicksort lavora per più che semplici numeri. Quickstart è un po 'più complicato di inserimento o bolla, ma è anche molto più efficiente nella maggior parte dei casi. Aspetta un secondo. Ha appena detto "più casi ", non" tutti "? È interessante notare, no. Non tutti i casi sono uguali. Non preoccupatevi di questo dettaglio, se si non hanno ancora visto la notazione O grande, ma Quicksort è un'operazione O (n al quadrato) algoritmo nel peggiore dei casi, proprio come inserimento o bubble sort. Tuttavia, tipicamente agisce molto più come un vecchio m algoritmo analogico. Perché? Torneremo più tardi. Ma per ora, facciamo solo imparare come funziona Quicksort. Quindi cerchiamo di camminare attraverso Quicksorting questo array di interi dal più piccolo al più grande. Qui abbiamo i numeri interi 6, 5, 1, 3, 8, 4, 7, 9, e 2. In primo luogo, prendiamo l'elemento finale del questo array - in questo caso, due - e chiamare il "pivot". Successivamente, abbiamo cominciare a guardare due cose - uno, il più basso indice, che mi riferirò come stare a destra del la parete, e, due, il più a sinistra elemento, che io chiamo la "corrente Elemento. "Quello che stiamo andando a fare è guardare tutti gli altri elementi, altri del pivot, e mettere tutti gli elementi minore del perno al sinistra del muro e tutti coloro maggiore del perno al destro della parete. Poi, finalmente, faremo cadere il perno proprio su quel muro per metterlo tra tutti i numeri inferiori a essa e tutti i numeri più grandi. Allora facciamolo. Sollevare il 2, mettere la parete di inizio, e chiamare il 6 la "corrente Elemento. "Allora vogliamo guardare il nostro elemento corrente, il 6. E poiché è più grande della 2, lasciamo lì a destro della parete. Poi, si passa a guardare il 5 come il nostro elemento corrente e vedere che questo è, di nuovo, più grande del pivot, quindi abbiamo lasciarla dove è sulla destra lato del muro. Ci muoviamo su. Il nostro elemento corrente è 1 ora, e - oh. Questo è diverso ora. L'elemento corrente è ora più piccolo il pivot, quindi vogliamo mettere a fianco della parete. Per fare questo, diciamo solo passare l' elemento corrente con l'indice più basso seduta appena a destra della parete. Ora, passiamo il muro alto un indice così l'1 è a sinistra lato del muro ora. Aspetta. Ho solo confuso gli elementi sulla lato destro del muro, no? Non ti preoccupare. Va bene. L'unica cosa che ci interessa per ora è che tutti questi elementi alla destra della parete sono più grandi del pivot. Nessun ordine reale è ancora assunta. Ora, tornando alla cernita. Così continuiamo a guardare il resto degli elementi. E in questo caso, si nota che ci sono altri elementi inferiore al pivot, così noi tutti lasciamo sulla il lato destro della parete. Infine, si arriva a l'elemento corrente e vedere che è il perno. Ora, ciò significa che abbiamo due sezioni della matrice, il primo essere piccola sul perno e sul lato sinistro della parete, e il secondo essere maggiore del perno al lato destro della parete. Vogliamo mettere l'elemento di cerniera tra i due, e poi sapremo che il perno è nella sua destra posto ordinato finale. Così passiamo il primo elemento sul lato destro della parete con il perno, e sappiamo che il perno nella sua posizione corretta. Abbiamo poi ripetere questo processo per l' subarrays a sinistra ea destra del pivot. Dall'ultima sottomatrice è unico lungo elemento, sappiamo che è già ordinato perché come si può essere fuori ordinare se sei solo elemento? Per il lato destro della sottomatrice abbiamo vedere che il perno è 5, e la parete è appena a sinistra del 6. E l'elemento corrente anche inizia come il 6. Quindi 6 è maggiore di 5. Lasciamo dove si trova il lato destro della parete. Ora, passando, 3 è inferiore a 5. Quindi passiamo con il primo elemento appena a destra della parete. Ora, ho spostato il muro alto uno. Ora, passare al 8. 8 è maggiore di 5, e così ci lasciamo. Il 4 è a meno di 5, quindi abbiamo accenderlo. E su. E su. Ogni volta che si ripete il processo sul lati sinistro e destro della matrice. noi scegliere un perno e fare i confronti e creare un altro livello di sinistra e subarrays destra. Questa chiamata ricorsiva continuerà fino si arriva alla fine, quando abbiamo diviso l'array globale in solo sottoarray di lunghezza 1. Da lì, sappiamo che l'array è ordinato perché ogni elemento ha, a certo punto, passato un perno. In altre parole, per ogni elemento, tutti i numeri a sinistra sono minori valori e tutti i numeri alla destra hanno valori superiori. Questo metodo funziona molto bene se l' valore del pivot scelto è circa a metà intervallo dei valori della lista. Ciò significa che, dopo ci muoviamo elementi intorno, ci sono circa altrettanti elementi a sinistra del perno come ci sono a destra. E la natura divide et impera del Algoritmo Quicksort viene poi ripreso massimo vantaggio. Questo crea una autonomia di O (n log n,) il n perché dobbiamo fare n meno 1 confronti di ogni generazione e di registro n perché dobbiamo dividere la lista log n volte. Tuttavia, nei casi peggiori, questa algoritmo può effettivamente essere O (n squadrato.) Supponiamo su ogni generazione, il perno così succede di essere il più piccolo o il più grande dei numeri stiamo ordinamento. Ciò significherebbe abbattere l'elenco n tempi e le decisioni n meno 1 confronti ogni volta. Quindi, o di n quadrati. Come possiamo migliorare il metodo? Un buon modo per migliorare il metodo è per ridurre la probabilità che il runtime è mai realmente o di n al quadrato. Ricordate questo peggiore, peggiore delle ipotesi può avvenire solo quando la perno scelto è sempre la massima o valore più basso nella matrice. Per garantire questo è meno probabile che accada, possiamo trovare il perno da scegliendo più elementi e prendendo il valore mediano. Il mio nome è Mark Grozen-Smith, e questo è CS50. Per semplicità, supponiamo che i le cose sono solo numeri interi, ma sapere che Quicksert - Quicksert? Scusi. Qui abbiamo i numeri interi 6, 5, 1, 3, 8, 4, 9. SPEAKER 1: Davvero? SPEAKER 2: non si fermano qui. SPEAKER 1: Davvero?