QuickSelect: el algoritmo de selección rápida explicado con ejemplos de código

¿Qué es QuickSelect?

QuickSelect es un algoritmo de selección para encontrar el K-ésimo elemento más pequeño en una lista sin clasificar.

El algoritmo explicado

Después de encontrar el pivote (una posición que divide la lista en dos partes: cada elemento de la izquierda es menor que el pivote y cada elemento de la derecha es más que el pivote), el algoritmo se repite solo para la parte que contiene el k-ésimo elemento más pequeño.

Si el índice del elemento particionado (pivote) es mayor que k, entonces el algoritmo se repite para la parte izquierda. Si el índice (pivote) es igual que k, entonces hemos encontrado el k-ésimo elemento más pequeño y se devuelve. Si el índice es menor que k, entonces el algoritmo se repite para la parte correcta.

Psudocódigo de selección

Input : List, left is first position of list, right is last position of list and k is k-th smallest element. Output : A new list is partitioned. quickSelect(list, left, right, k) if left = right return list[left] // Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 

Dividir

La partición es encontrar el pivote como se mencionó anteriormente. (Cada elemento de la izquierda es menor que el pivote y cada elemento de la derecha es más que pivote) Hay dos algoritmos para encontrar el pivote de la partición.

  • Partición Lomuto
  • Partición Hoare

Partición Lomuto

Esta partición elige un pivote que suele ser el último elemento de la matriz. El algoritmo mantiene el índice i mientras escanea la matriz usando otro índice j, de modo que los elementos lo a i (inclusive) son menores o iguales al pivote, y los elementos i + 1 a j-1 (inclusive) son mayores que el pivote.

Este esquema se degrada O(n^2)cuando la matriz ya está en orden.

algorithm Lomuto(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] < pivot then if i != j then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i 

Partición Hoare

Hoare usa dos índices que comienzan en los extremos de la matriz que se está particionando, luego se mueven uno hacia el otro hasta que detectan una inversión: un par de elementos, uno mayor o igual al pivote, uno menor o igual al pivote, que están en el orden incorrecto entre sí.

Luego se intercambian los elementos invertidos. Cuando los índices se encuentran, el algoritmo se detiene y devuelve el índice final. Hay muchas variantes de este algoritmo.

algorithm Hoare(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i]  pivot if i >= j then return j swap A[i] with A[j]