Che cosa rende un caso negativo per l'ordinamento rapido?

Ogni algoritmo di ordinamento ha il peggio, e in molti casi il caso peggiore è davvero pessimo, quindi vale la pena provarlo. Il problema è che non esiste un singolo caso peggiore solo perché si conosce l'algoritmo di base.

I casi peggiori comuni includono: già ordinati; ordinato al contrario; quasi ordinato, un elemento fuori servizio; tutti i valori sono uguali; lo stesso eccetto il primo (o l'ultimo) è più alto (o più basso). Una volta avevamo un tipo in cui il caso peggiore era un particolare pattern a dente di sega, che era molto difficile da prevedere, ma abbastanza comune nella pratica.

Il caso peggiore per quicksort è quello che ottiene sempre il peggior pivot possibile, in modo che una delle partizioni abbia un solo elemento. Se il pivot è il primo elemento (scelta sbagliata), i dati ordinati già ordinati o inversi sono i peggiori. Per i dati di pivot della mediana di tre che sono tutti uguali o solo il primo o l'ultimo è diverso il trucco.

Per quicksort la complessità media è nlogn e il caso peggiore è n ^ 2. Il motivo per cui vale la pena innescare il comportamento del caso peggiore è perché questo è anche il caso che produce la massima profondità di ricorsione. Per un'implementazione ingenua la profondità di ricorsione potrebbe essere n, che potrebbe innescare un eccesso di stack. Testare altre situazioni estreme (incluso il caso migliore) può valerne la pena per ragioni simili.

Un algoritmo scappa dalla maggior parte dei casi brutti usando un pivot randomizzato, escludendo elementi continui equivale a un pivot dal partizionamento, e ricerca asimmetrica. Cerca in avanti un elemento maggiore o uguale a un pivot, e ricerca all'indietro un elemento inferiore a un pivot.
Ringrazio Michele, la ricerca asimmetrica è concepita per risolvere [2,1,2,1,2,1,2,1].

Il seguente risultato è generato dalla mia funzione qsort_random (). N = 100.000

usec    call   compare   copy    pattern
80132   62946  1971278   877143  random
47326   57578  1606067   215155  sorted : 0,1,2,3,...,n-1
49927   63578  1628883   338715  sorted in reverse : n-1,n-2,...,2,1,0
55619   63781  1596934   377330  nearly reverse : n-2,n-1,n-4,n-3,...,2,3,0,1
54714   66667  1611454   290392  median-3-killer : n-1,0,1,2,...,n-2
1491    1      99999     4       all values the same : n,n,n,...
1577    1      99999     4       first is higher : n,1,1,1,...
2778    2      156159    10      last is lower : n,n,n,...,n,1
2994    3      199996    100009  a few data : n,...,n,1,...,1
3196    3      199996    50012   zigzag : n,1,n,1,...,n,1
917796  56284  67721985  673356  valley(sawtooth?) : n-1,n-3,...,0,...,n-4,n-2

La maggior parte dei casi è più veloce di un modello casuale. Il pattern Valley è un caso negativo per la maggior parte della selezione pivot.

qsort(3)       usec = 14523   call = 0      compare = 884463    copy = 0
qsort_head()   usec = 138609  call = 99999  compare = 8120991   copy = 1214397
qsort_middle() usec = 664325  call = 99999  compare = 52928111  copy = 1036047
qsort_trad()   usec = 118122  call = 99999  compare = 6476025   copy = 1337523
qsort_random() usec = 295699  call = 58806  compare = 19439952  copy = 732962
qsort_log2()   usec = 66411   call = 63987  compare = 1597455   copy = 944821

qsort_log2 () esegue l'escape dal caso errato selezionando un pivot negli elementi log2 (N).
qsort (3) usa la libreria GNU che è un ordinamento di tipo merge di ordinamento indice.
qsort_trad () seleziona un pivot negli elementi first, middle e last.
qsort_random () e qsort_log2 () non usano lo swapping.
I programmi e gli script di Source C sono pubblicati in github .