QuickSelect Algorithm Understanding

Question

Ho esaminato vari tutorial e articoli che discutono di quicksort e quickselect, tuttavia la mia comprensione di essi è ancora traballante.

Data questa struttura di codice, ho bisogno di essere in grado di cogliere e spiegare come funziona quickselect.

// return the kth smallest item 
int quickSelect(int items[], int first, int last, int k) { 
    int pivot = partition(items, first, last); 
    if (k < pivot-first) { 
     return quickSelect(items, first, pivot, k); 
    } else if (k > pivot) { 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } else { 
     return items[k]; 
    } 
} 

Ho bisogno di un piccolo aiuto con ripartita per circa il pseudo-codice, e mentre io non sono stato fornito con il codice funzione di partizione, mi piacerebbe capire cosa avrebbe fatto data la funzione quickselect fornito.

So come funziona quicksort, ma non solo quickselect. Il codice che ho appena fornito è un esempio che ci è stato dato su come formattare la selezione rapida.

EDIT: Il codice corretto è

int quickSelect(int items[], int first, int last, int k) 
{ 
    int pivot = partition(items, first, last); 
    if (k < pivot-first+1) 
    { //boundary was wrong 
     return quickSelect(items, first, pivot, k); 
    } 
    else if (k > pivot-first+1) 
    {//boundary was wrong 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } 
    else 
    { 
     return items[pivot];//index was wrong 
    } 
} 

courtesty: @Haitao

Answer 1

La parte importante nella Selezione rapida è partizione. Quindi lascia che ti spieghi prima.

Partizione in selezioni rapide a pivot (in modo casuale o primo/ultimo elemento). Quindi riorganizza l'elenco in modo che tutti gli elementi inferiori a pivot siano sul lato sinistro del pivot e altri sulla destra. Quindi restituisce l'indice dell'elemento pivot.

Ora qui troviamo il kth più piccolo elemento. Dopo casi di partizione:

1. k == pivot. Allora hai già trovato kth il più piccolo. Questo perché il modo in cui funziona la partizione. Esistono esattamente gli elementi k - 1 che sono più piccoli dell'elemento kth.
2. k < pivot. Quindi kth il più piccolo è sul lato sinistro di pivot.
3. k > pivot. Quindi kth il più piccolo è sul lato destro del pivot. E per trovarlo devi trovare il numero più piccolo sulla destra, k-pivot.

Answer 2

partizione è abbastanza semplice: riorganizza gli elementi in modo quelli meno un perno selezionato sono a indici inferiori nella matrice del pivot e quelle maggiore del perno sono a indice superiore della matrice.

Ho parlato del resto in un previous answer.

Answer 3

btw, il codice ha qualche bug ..

int quickSelect(int items[], int first, int last, int k) { 
    int pivot = partition(items, first, last); 
    if (k < pivot-first+1) { //boundary was wrong 
     return quickSelect(items, first, pivot, k); 
    } else if (k > pivot-first+1) {//boundary was wrong 
     return quickSelect(items, pivot+1, last, k-pivot); 
    } else { 
     return items[pivot];//index was wrong 
    } 
} 

Answer 4

int quickSelect(int A[], int l, int h,int k) 
{ 
     int p = partition(A, l, h); 
     if(p==(k-1)) return A[p]; 
     else if(p>(k-1)) return quickSelect(A, l, p - 1,k); 
     else return quickSelect(A, p + 1, h,k); 

} 

// funzione di partizione stessa di QuickSort

Answer 5

Potete trovare QuickSelect here utilizzando 3 vie partizionamento.

Il codice è scritto in Scala. Inoltre, aggiungerò altri algoritmi e strutture dati nel mio viaggio per padroneggiare l'argomento.

Si può anche notare che esiste una funzione mediana per gli array con un numero dispari di elementi implementati usando quickSelect.

edit: E 'richiesto di mischiare l'array per garantire un tempo di esecuzione medio lineare

Answer 6

int partition(vector<int> &vec, int left, int right, int pivotIndex) 
{ 
     int pivot = vec[pivotIndex]; 
     int partitionIndex = left; 

     swap(vec[pivotIndex],vec[right]); 
     for(int i=left; i < right; i++) { 
       if(vec[i]<pivot) { 
         swap(vec[i],vec[partitionIndex]); 
         partitionIndex++; 
       } 
     } 
     swap(vec[partitionIndex], vec[right]); 

     return partitionIndex; 
} 

int select(vector<int> &vec, int left, int right, int k) 
{ 
     int pivotIndex; 
     if (right == left) { 
       return vec[left]; 
     } 
     pivotIndex = left + rand() % (right-left); 

     pivotIndex = partition(vec,left,right,pivotIndex); 
     if (pivotIndex == k) { 
       return vec[k]; 
     } else if(k<pivotIndex) { 
       /*k is present on the left size of pivotIndex*/ 
       return partition(vec,left,pivotIndex-1, k); 
     } else { 
       /*k occurs on the right size of pivotIndex*/ 
       return partition(vec, pivotIndex+1, right, k); 
     } 
     return 0; 
}