algorithm - quick select geeks for geeks

QuickSelect Algorithm Understanding

Question

He estado estudiando detenidamente varios tutoriales y artículos que tratan sobre el ordenamiento rápido y la selección rápida, sin embargo, mi comprensión de ellos sigue siendo inestable.

Dada esta estructura de código, necesito poder comprender y explicar cómo funciona la selección rápida.

// 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 para dividirme en pseudocódigo, y aunque no se me ha proporcionado el código de función de partición, me gustaría entender qué haría si se proporcionara la función de selección rápida.

Sé cómo funciona la ordenación rápida, pero no la selección rápida. El código que acabo de proporcionar es un ejemplo que nos dieron sobre cómo formatear la selección rápida.

EDITAR: 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
    }
}

Corteza: @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 la selección rápida selecciona un pivot (ya sea al azar o al primer / último elemento). Luego, reorganiza la lista de manera que todos los elementos menos que pivot estén en el lado izquierdo del pivote y otros en el derecho. A continuación, devuelve el índice del elemento de pivot .

Ahora aquí estamos encontrando 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 se debe a la forma en que funciona la partición. Hay exactamente k - 1 elementos que son más pequeños que el elemento kth .
2. k < pivot . Entonces, el kth más pequeño está en el lado izquierdo del pivot .
3. k > pivot . Entonces, el kth más pequeño está en el lado derecho del pivote. Y para encontrarlo, debes encontrar el número más pequeño de k-pivot a la derecha.

Answer 2

La partición es bastante simple: reorganiza los elementos para que aquellos que no sean un pivote seleccionado estén en índices más bajos en la matriz que el pivote y los más grandes que el pivote estén en índices más altos en la matriz.

Hablé del resto en una respuesta anterior .

Answer 3

Puede encontrar quickSelect here utilizando la partición de 3 vías.

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 de mediana para arreglos con un número impar de elementos implementados usando quickSelect.

edición: se requiere barajar la matriz para garantizar un tiempo de ejecución promedio lineal

Answer 4

por cierto, su 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 5

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

Answer 6

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 igual que QuickSort