Osservazione del comportamento quadratico con quicksort - O (n^2)

Question

L'algoritmo quicksort ha una complessità temporale media O (n * log (n)) e una complessità del caso peggiore O (n^2).

Supponendo alcune varianti dell'algoritmo quicksort di Hoare, quali tipi di input causeranno l'algoritmo di quicksort per mostrare la complessità del caso peggiore?

Si prega di indicare qualsiasi ipotesi relativa ai dettagli di implementazione riguardanti l'algoritmo di quicksort specifico come la selezione pivot, ecc. O se proviene da una libreria comunemente disponibile come libc.

Alcuni lettura

1. A Killer Adversary for Quicksort
2. Quicksort Is Optimal
3. Engineering a Sort Function
4. Introspective Sorting and Selection Algorithms

Answer 1

I Quick sort esegue peggiore cioè, a O (n^2) quando tutti i valori di il perno scelto è il più grande o il più piccolo del t insieme Considera questo esempio.

Il perno prescelto dire è 1, si avrà 4 elementi sul lato destro del perno e senza elementi sul lato sinistro. Applicando questa stessa logica in modo ricorsivo e il pivot scelto è 2, 3, 4, 5 rispettivamente, abbiamo raggiunto una situazione in cui questo tipo si è svolto nel momento peggiore possibile.

È stato consigliato e dimostrato che Quicksort funziona bene se l'input viene mischiato correttamente.

Inoltre, la selezione di un tipo di solito dipende da una chiara conoscenza del dominio di input. Ad esempio, se l'input è enorme, c'è qualcosa chiamato external sort che può usare la memoria esterna. Se la dimensione di input è molto piccola, potremmo optare per un ordinamento di tipo merge ma non per set di input medi e grandi poiché utilizza memoria extra. Il principale vantaggio di Quick sort è il suo significato "sul posto", non viene utilizzata memoria aggiuntiva per i dati di input. Il suo peggior tempo su carta è O (n^2), ma è ancora ampiamente preferito e usato. Il mio punto qui è che gli algoritmi di ordinamento possono essere modificati in base alla conoscenza del set di input ed è una questione di preferenza.

Answer 2

Per espandere su ciò che ha detto Bragboy, anziché solo in esecuzione:

quicksort(array); 

Run:

shuffle(array); 
quicksort(array); 

Dove la definizione di shuffle() potrebbe essere:

shuffle(array){ 
    for(int i = array.length; i > 0; i--){ 
     r= random number % i; 
     swap(array[i], array[r]); 
    } 
} 

In questo modo si , probabilmente, si occupa del caso di ottenere input che rende quicksort() lento.

Answer 3

L'algoritmo di Quicksort di Hoare sceglie un pivot casuale. Per risultati riproducibili suggerirei la modifica di Scowen che, tra le altre cose, sceglie la voce centrale dall'input.Per questa variante, uno schema a dente di sega con il perno più piccolo sembra essere l'input peggiore:

starting with   { j i h g f a e d c b } 
compare 1 to 6   { (j) i h g f (a) e d c b } 
compare 6 to 10   { j i h g f (a) e d c (b) } 
compare 6 to 9   { j i h g f (a) e d (c) b } 
compare 6 to 8   { j i h g f (a) e (d) c b } 
compare 6 to 7   { j i h g f (a) (e) d c b } 
swap 1<=>6    { (a) i h g f (j) e d c b } 
compare 1 to 5   { (a) i h g (f) j e d c b } 
compare 1 to 4   { (a) i h (g) f j e d c b } 
compare 1 to 3   { (a) i (h) g f j e d c b } 
compare 1 to 2   { (a) (i) h g f j e d c b } 
compare 2 to 6   { a (i) h g f (j) e d c b } 
compare 3 to 6   { a i (h) g f (j) e d c b } 
compare 4 to 6   { a i h (g) f (j) e d c b } 
compare 5 to 6   { a i h g (f) (j) e d c b } 
compare and swap 6<=>10 { a i h g f (b) e d c (j) } 
compare 7 to 10   { a i h g f b (e) d c (j) } 
compare 8 to 10   { a i h g f b e (d) c (j) } 
compare 9 to 10   { a i h g f b e d (c) (j) } 
compare 2 to 6   { a (i) h g f (b) e d c j } 
compare 6 to 9   { a i h g f (b) e d (c) j } 
compare 6 to 8   { a i h g f (b) e (d) c j } 
compare 6 to 7   { a i h g f (b) (e) d c j } 
swap 2<=>6    { a (b) h g f (i) e d c j } 
compare 2 to 5   { a (b) h g (f) i e d c j } 
compare 2 to 4   { a (b) h (g) f i e d c j } 
compare 2 to 3   { a (b) (h) g f i e d c j } 
compare 3 to 6   { a b (h) g f (i) e d c j } 
compare 4 to 6   { a b h (g) f (i) e d c j } 
compare 5 to 6   { a b h g (f) (i) e d c j } 
compare and swap 6<=>9 { a b h g f (c) e d (i) j } 
compare 7 to 9   { a b h g f c (e) d (i) j } 
compare 8 to 9   { a b h g f c e (d) (i) j } 
compare 3 to 6   { a b (h) g f (c) e d i j } 
compare 6 to 8   { a b h g f (c) e (d) i j } 
compare 6 to 7   { a b h g f (c) (e) d i j } 
swap 3<=>6    { a b (c) g f (h) e d i j } 
compare 3 to 5   { a b (c) g (f) h e d i j } 
compare 3 to 4   { a b (c) (g) f h e d i j } 
compare 4 to 6   { a b c (g) f (h) e d i j } 
compare 5 to 6   { a b c g (f) (h) e d i j } 
compare and swap 6<=>8 { a b c g f (d) e (h) i j } 
compare 7 to 8   { a b c g f d (e) (h) i j } 
compare 4 to 6   { a b c (g) f (d) e h i j } 
compare 6 to 7   { a b c g f (d) (e) h i j } 
swap 4<=>6    { a b c (d) f (g) e h i j } 
compare 4 to 5   { a b c (d) (f) g e h i j } 
compare 5 to 6   { a b c d (f) (g) e h i j } 
compare and swap 6<=>7 { a b c d f (e) (g) h i j } 
compare and swap 5<=>6 { a b c d (e) (f) g h i j }