Selección rápida es un algoritmo de selección para encontrar el k-ésimo elemento más pequeño en una lista desordenada. Está relacionado con el ordenación rápida Algoritmo de clasificación.
Ejemplos:

Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 7 Input: arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output: 10 

El algoritmo es similar a QuickSort. La diferencia es que, en lugar de repetirse para ambos lados (después de encontrar el pivote), se repite solo para la parte que contiene el k-ésimo elemento más pequeño. La lógica es simple, si el índice del elemento particionado es mayor que k, entonces recurrimos para la parte izquierda. Si el índice es igual a k, hemos encontrado el k-ésimo elemento más pequeño y regresamos. Si el índice es menor que k, entonces recurrimos a la parte derecha. Esto reduce la complejidad esperada de O(n log n) a O(n), con el peor de los casos de O(n^2).

function 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  C++14       // CPP program for implementation of QuickSelect  #include  using namespace std;    // Standard partition process of QuickSort().  // It considers the last element as pivot  // and moves all smaller element to left of  // it and greater elements to right  int partition(int arr[], int l, int r)  {   int x = arr[r], i = l;   for (int j = l; j  <= r - 1; j++) {   if (arr[j]  <= x) {   swap(arr[i], arr[j]);   i++;   }   }   swap(arr[i], arr[r]);   return i;  }    // This function returns k'th smallest  // element in arr[l..r] using QuickSort  // based method. ASSUMPTION: ALL ELEMENTS  // IN ARR[] ARE DISTINCT  int kthSmallest(int arr[], int l, int r, int k)  {   // If k is smaller than number of   // elements in array   if (k>0 &&k <= r - l + 1) {     // Partition the array around last   // element and get position of pivot   // element in sorted array   int index = partition(arr, l, r);     // If position is same as k   if (index - l == k - 1)   return arr[index];     // If position is more, recur   // for left subarray   if (index - l>k - 1) return kthSmallest(arr, l, index - 1, k);     // De lo contrario, se repetirá para el subarreglo derecho return kthSmallest(arr, index + 1, r, k - index + l - 1);   } // Si k es mayor que el número de // elementos en la matriz, devuelve INT_MAX;  } // Programa controlador para probar los métodos anteriores int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 };   int n = tamaño de (arr) / tamaño de (arr [0]);   int k = 3;   corte < < 'K-th smallest element is '   < < kthSmallest(arr, 0, n - 1, k);   return 0;  }   Java       // Java program of Quick Select  import java.util.Arrays;    class GFG {     // partition function similar to quick sort   // Considers last element as pivot and adds   // elements with less value to the left and   // high value to the right and also changes   // the pivot position to its respective position   // in the final array.   public static int partition(int[] arr, int low,   int high)   {   int pivot = arr[high], pivotloc = low;   for (int i = low; i  <= high; i++) {   // inserting elements of less value   // to the left of the pivot location   if (arr[i]   int temp = arr[i];   arr[i] = arr[pivotloc];   arr[pivotloc] = temp;   pivotloc++;   }   }     // swapping pivot to the final pivot location   int temp = arr[high];   arr[high] = arr[pivotloc];   arr[pivotloc] = temp;     return pivotloc;   }     // finds the kth position (of the sorted array)   // in a given unsorted array i.e this function   // can be used to find both kth largest and   // kth smallest element in the array.   // ASSUMPTION: all elements in arr[] are distinct   public static int kthSmallest(int[] arr, int low,   int high, int k)   {   // find the partition   int partition = partition(arr, low, high);     // if partition value is equal to the kth position,   // return value at k.   if (partition == k - 1)   return arr[partition];     // if partition value is less than kth position,   // search right side of the array.   else if (partition 1)   return kthSmallest(arr, partition + 1, high, k);     // if partition value is more than kth position,   // search left side of the array.   else  return kthSmallest(arr, low, partition - 1, k);   }     // Driver Code   public static void main(String[] args)   {   int[] array = new int[] { 10, 4, 5, 8, 6, 11, 26 };   int[] arraycopy   = new int[] { 10, 4, 5, 8, 6, 11, 26 };     int kPosition = 3;   int length = array.length;     if (kPosition>longitud) { System.out.println('Índice fuera de límite');   } else { // encuentra el késimo valor más pequeño System.out.println( 'K-ésimo elemento más pequeño en la matriz: ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // Este código es una contribución de Saiteja Pamulapati Python3 # Programa Python3 de Quick Select # Proceso de partición estándar de QuickSort().  # Considera el último elemento como pivote # y mueve todos los elementos más pequeños a la izquierda # y los elementos mayores a la derecha def partición(arr, l, r): x = arr[r] i = l for j in range(l, r): si arr[j] <= x:   arr[i], arr[j] = arr[j], arr[i]   i += 1    arr[i], arr[r] = arr[r], arr[i]   return i    # finds the kth position (of the sorted array)  # in a given unsorted array i.e this function  # can be used to find both kth largest and  # kth smallest element in the array.  # ASSUMPTION: all elements in arr[] are distinct  def kthSmallest(arr, l, r, k):     # if k is smaller than number of   # elements in array   if (k>0 yk <= r - l + 1):     # Partition the array around last   # element and get position of pivot   # element in sorted array   index = partition(arr, l, r)     # if position is same as k   if (index - l == k - 1):   return arr[index]     # If position is more, recur   # for left subarray   if (index - l>k - 1): return kthSmallest(arr, l, index - 1, k) # De lo contrario, se repetirá para el subarreglo derecho return kthSmallest(arr, index + 1, r, k - index + l - 1) print('Index out of enlazado') # Código del controlador arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-ésimo elemento más pequeño es ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Este código es una contribución de Muskan Kalra.   C# // Programa C# de Selección Rápida usando System;    class GFG { // función de partición similar a la clasificación rápida // Considera el último elemento como pivote y agrega // elementos con menos valor a la izquierda y // valor alto a la derecha y también cambia // la posición del pivote a su posición respectiva / / en la matriz de solo lectura.   particiones estáticas int(int []arr,int bajo, int alto) { int pivot = arr[alto], pivotloc = bajo, temp;   para (int i = bajo; i <= high; i++)   {   // inserting elements of less value   // to the left of the pivot location   if(arr[i]   {   temp = arr[i];   arr[i] = arr[pivotloc];   arr[pivotloc] = temp;   pivotloc++;   }   }     // swapping pivot to the readonly pivot location   temp = arr[high];   arr[high] = arr[pivotloc];   arr[pivotloc] = temp;     return pivotloc;   }     // finds the kth position (of the sorted array)   // in a given unsorted array i.e this function   // can be used to find both kth largest and   // kth smallest element in the array.   // ASSUMPTION: all elements in []arr are distinct   static int kthSmallest(int[] arr, int low,   int high, int k)   {   // find the partition   int partition = partitions(arr,low,high);     // if partition value is equal to the kth position,   // return value at k.   if(partition == k)   return arr[partition];     // if partition value is less than kth position,   // search right side of the array.   else if(partition   return kthSmallest(arr, partition + 1, high, k );     // if partition value is more than kth position,   // search left side of the array.   else  return kthSmallest(arr, low, partition - 1, k );   }     // Driver Code   public static void Main(String[] args)   {   int[] array = {10, 4, 5, 8, 6, 11, 26};   int[] arraycopy = {10, 4, 5, 8, 6, 11, 26};     int kPosition = 3;   int length = array.Length;     if(kPosition>longitud) { Console.WriteLine('Índice fuera de límite');   } else { // encuentra el késimo valor más pequeño Console.WriteLine('K-ésimo elemento más pequeño en la matriz: ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // Este código es aportado por 29AjayKumar Javascript // Programa Javascript de selección rápida // función de partición similar a la ordenación rápida // Considera el último elemento como pivote y agrega // elementos con menos valor a la izquierda y // valor alto a la derecha y también cambia // la posición del pivote a su posición respectiva // en la matriz final.  function _partition(arr, low, high) { let pivot = arr[high], pivotloc = low;   para (sea i = bajo; i <= high; i++)   {     // inserting elements of less value   // to the left of the pivot location   if (arr[i]   {   let temp = arr[i];   arr[i] = arr[pivotloc];   arr[pivotloc] = temp;   pivotloc++;   }   }     // swapping pivot to the final pivot location   let temp = arr[high];   arr[high] = arr[pivotloc];   arr[pivotloc] = temp;     return pivotloc;  }    // finds the kth position (of the sorted array)   // in a given unsorted array i.e this function   // can be used to find both kth largest and   // kth smallest element in the array.   // ASSUMPTION: all elements in arr[] are distinct  function kthSmallest(arr, low, high, k)  {     // find the partition   let partition = _partition(arr, low, high);     // if partition value is equal to the kth position,   // return value at k.   if (partition == k - 1)   return arr[partition];     // if partition value is less than kth position,   // search right side of the array.   else if (partition   return kthSmallest(arr, partition + 1, high, k);     // if partition value is more than kth position,   // search left side of the array.   else  return kthSmallest(arr, low, partition - 1, k);  }    // Driver Code  let array = [ 10, 4, 5, 8, 6, 11, 26];  let arraycopy = [10, 4, 5, 8, 6, 11, 26 ];  let kPosition = 3;  let length = array.length;    if (kPosition>longitud) { document.write('Índice fuera de límite ');  } else { // encuentra el késimo valor más pequeño document.write( 'K-ésimo elemento más pequeño en la matriz: ' + kthSmallest(arraycopy, 0, length - 1, kPosition)+' ');  } // Este código es una contribución de rag2127 Salida: K-ésimo elemento más pequeño es 6 Puntos importantes: Al igual que la clasificación rápida, es rápido en la práctica, pero tiene un rendimiento deficiente en el peor de los casos. Se utiliza en El proceso de partición es el mismo que QuickSort, solo difiere el código recursivo. Existe un algoritmo que encuentra el k-ésimo elemento más pequeño en O(n) en el peor de los casos, pero QuickSelect funciona mejor en promedio.    Función C++ relacionada: std::nth_element en C++