miglioramento algoritmo di ordinamento rapido se più chiavi duplicate

Question

Sto leggendo l'algoritmo di ordinamento rapido nel libro di Robert Sedwick Algorithms e le strutture di dati parte 1-4.

template <class item> 

static void quicksort(item [] a, int l, int r) 
{ 
    if(r <= l) return; 
    int i = partition(a,l,r); 
    quicksort(a, l, i-1); 
    quicksort(a, i+1, r); 
} 

template <class item> 
int partition(item a[], int l, int r) 
{ 
    int i = l-1; j = r; item v = a[r]; 

    for(;;) { 
     while(a[++i] < v); 
     while(v < a[--j]) 
      if(j == l) 
       break; 
     if(i >= j) 
      break; // pointer crossing. 
     exch(a[i], a[j]); 
    } 

    exch(a[i], a[r]); 
    return i; 
} 

Il libro ha il seguente testo sopra l'algoritmo.

Quando le chiavi duplicate sono presenti nel file, il passaggio del puntatore è sottile. potremmo migliorare leggermente il processo di partizionamento da terminando le scansioni quando ho < j, e quindi usando j, piuttosto che i-1, per delimitare l'estremità destra del subfile sinistro per la prima chiamata ricorsiva . Lasciare il ciclo iterare ancora una volta in questo caso è un miglioramento , perché, quando mai i cicli di scansione terminano con j e mi riferisco allo stesso elemento, finiamo con due elementi in le loro posizioni finali: l'elemento che si è fermato entrambe le scansioni, che devono essere uguali all'elemento di partizionamento e l'elemento di partizionamento stesso. È probabile che questo cambiamento valga la pena, perché, in questo caso particolare, il programma lascia un record con una chiave uguale alla chiave di partizionamento in un [r] e che rende la prima partizione nella chiamata quick-sort (a , i + 1, r) degenera, perché la sua chiave più a destra è la più piccola.

Le mie domande sono

1. Come possiamo modificare sopra programma con la descrizione di seguito? Ho difficoltà a modificarlo per capire il testo.
2. Perché sopra l'algoritmo di ordinamento rapido non funziona in modo efficace se sono presenti più chiavi duplicate.
3. Come sopra la modifica migliora se sono presenti più chiavi di duplicazione?
4. Cosa significa autore per "la prima partizione nella chiamata quick-sort (a, i + 1, r) degenera, perché la sua chiave più a destra è la più piccola". ? Cosa significa autore degenera qui?

Grazie per il vostro tempo e aiuto.

Answer 1

>> Perché sopra l'algoritmo di ordinamento rapido non funziona in modo efficace se sono presenti più chiavi duplicate?

Essa diventa inefficiente, perché la sua condizione di rottura è: if(i >= j) break;
così, come si esegue la scansione da entrambi i lati con i e j, è del tutto possibile che si rompe quando i == j invece di lasciare i superano over j.

Che male potrebbe accadere quando ci si infrangono sulla i==j quando molte chiavi duplicate sono presenti?

quando si interrompe per i==j; dal primo ciclo while devi avere avuto a[i] >= v e dal secondo ciclo while a[j] <=v ma dato che stiamo considerando una 'pausa' per: i==j modo, vale a dire è uguale a v, l'elemento di rotazione .

In tale scenario, lo exch(a[i], a[r]); più esterno scambierà semplicemente il valore pivot su se stesso.
Quindi, nella tua prossima chiamata ricorsiva quicksort(a, i+1, r); per la metà destra dell'array, avresti un elemento minimo seduto all'estremità destra (la strategia di scelta pivot è semplicemente, item v = a[r];) e sappiamo tutti che non è corretto scegliere QuickSort un elemento di rotazione che corrisponde al minimo o al massimo della matrice. Quindi, la tua successiva chiamata ricorsiva per metà destra sarà una degenerata.
Ecco perché l'autore consiglia di non rompere per i == j ma prenderli prima che ciò accada.

>> Cosa significa autore degenera qui?

Degenerare qui significa che l'albero di ricorsione si sta inclinando, i problemi successivi non vengono generati di dimensioni quasi uguali. Si sta dividendo un problema di dimensioni N in qualcosa come problemi di dimensioni N-1 e 1 invece di qualcosa di più bilanciato, come dividerlo in problemi di dimensioni N/2 e N/2.

>> Come è possibile modificare il programma di cui sopra con la descrizione di seguito?

Potremmo implementarlo come segue:

int partition(int A[], int l, int r){ 
     int i=l-1, j=r, v = A[r]; 
     for(;;){ 
       while(A[++i] < v); 
       while(A[--j] > v) 
         if(j == l) 
           break; 
       if(i>=j) 
         break; 
       swap(A[i], A[j]); 
     } 
     if(i == j){// case when we stopped at the pivot element. 
       j = j+1;//backtrack j 1 step. 
       if(j <= r) 
        swap(A[j], A[r]); 
       return j;// partition the subsequent problems around j now. 
     } 
     swap(A[i], A[r]); 
     return i; 
} 

>> Come sopra modifica migliorare se più duplicazione chiavi sono presenti?
Migliora le prestazioni consentendo di NON generare uno scenario ovvio di caso degenerato.