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