Algoritmo QuickSelect Comprensión

Question

He estado estudiando detenidamente varios tutoriales y artículos que tratan de quicksort y quickselect, sin embargo mi comprensión de ellos todavía es inestable.

Dada esta estructura de código, necesito ser capaz de captar y explicar cómo funciona 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]; 
    } 
} 

Necesito un poco de ayuda con que se dividen en pseudo-código, y mientras no se me ha proporcionado con el código de función de partición, me gustaría entender lo que haría dada la función Quickselect proporcionado.

Sé cómo funciona quicksort, simplemente no quickselect. El código que acabo de proporcionar es un ejemplo que se nos dio sobre cómo formatear la selección rápida.

EDIT: El código corregido es

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 en la selección rápida es la partición. Así que déjame explicarte eso primero.

La partición en selección rápida selecciona un pivot (ya sea al azar o primero/último elemento). Luego reorganiza la lista de manera que todos los elementos con menos de pivot estén en el lado izquierdo del pivote y otros en el derecho. A continuación, devuelve el índice del elemento pivot.

Ahora aquí estamos encontrando kth el elemento más pequeño. Después de los casos de partición son:

1. k == pivot. Entonces ya has encontrado kth más pequeño. Esto es porque la forma en que la partición está funcionando. Hay exactamente k - 1 elementos que son más pequeños que el elemento kth.
2. k < pivot. Entonces kth más pequeño está en el lado izquierdo de pivot.
3. k > pivot. Entonces kth más pequeño está en el lado derecho del pivote. Y para encontrarlo, en realidad tiene que encontrar k-pivot el número más pequeño a la derecha.

Answer 2

La partición es bastante simple: reorganiza los elementos de modo que los que menos que un pivote seleccionado están en índices inferiores en el arreglo que el pivote y los más grandes que el pivote están en índices más altos en el conjunto.

Hablé sobre el resto en un previous answer.

Answer 3

por cierto, el código tiene algunos errores ..

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); 

} 

// función de partición mismo que QuickSort

Answer 5

puede encontrar QuickSelect here usando 3 vías de partición.

El código está escrito en Scala. Además, agregaré más algoritmos y estructuras de datos en mi viaje para dominar el tema.

También puede observar que hay una función mediana para las matrices con un número impar de elementos implementados con quickSelect.

edición: Se requiere para mezclar la matriz para garantizar un tiempo medio de funcionamiento lineal

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; 
}