Selectare rapidă este un algoritm de selecție pentru a găsi cel mai mic element k-lea dintr-o listă neordonată. Este legat de sortare rapida algoritm de sortare.
Exemple:

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

Algoritmul este similar cu QuickSort. Diferența este că, în loc să se repete pentru ambele părți (după găsirea pivotului), aceasta se repetă numai pentru partea care conține cel mai mic element k-lea. Logica este simplă, dacă indicele elementului partiționat este mai mare de k, atunci revenim pentru partea din stânga. Dacă indicele este același cu k, am găsit cel mai mic element k-lea și revenim. Dacă indicele este mai mic decât k, atunci revenim pentru partea dreaptă. Acest lucru reduce complexitatea așteptată de la O(n log n) la O(n), cu cel mai rău caz 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) returnează kthSmallest(arr, l, index - 1, k);     // Altfel, se repetă pentru subbarajul din dreapta return kthSmallest(arr, index + 1, r, k - index + l - 1);   } // Dacă k este mai mare decât numărul // de elemente din tablou returnează INT_MAX;  } // Program driver pentru a testa metodele de mai sus int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 };   int n = sizeof(arr) / sizeof(arr[0]);   int k = 3;   cout < < '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>lungime) { System.out.println('Index out of bound');   } else { // găsiți a k-a cea mai mică valoare System.out.println( 'K-a cel mai mic element din matrice: ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // Acest cod este contribuit de Saiteja Pamulapati Python3 # Programul Python3 al Quick Select # Procesul de partiție standard al QuickSort().  # Consideră ultimul element ca pivot # și mută toate elementele mai mici la stânga # și elementele mai mari la dreapta def partition(arr, l, r): x = arr[r] i = l pentru j în interval (l, r): dacă 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 și k <= 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) # Altfel se repetă pentru subbary dreapta return kthSmallest(arr, index + 1, r, k - index + l - 1) print('Index out of bound') # Cod driver arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-al-lea cel mai mic element este ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Acest cod este contribuit de Muskan Kalra.   C# // Programul C# de Selectare rapidă folosind System;    class GFG { // funcție de partiție similară cu sortarea rapidă // Consideră ultimul element ca pivot și adaugă // elemente cu valoare mai mică la stânga și // valoare mare la dreapta și, de asemenea, schimbă // poziția pivot în poziția sa respectivă / / în matricea doar pentru citire.   static int partitions(int []arr,int low, int high) { int pivot = arr[high], pivotloc = low, temp;   pentru (int i = scăzut; 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>lungime) { Console.WriteLine('Index out of bound');   } else { // găsiți a k-a cea mai mică valoare Console.WriteLine('K-a cel mai mic element din matrice : ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // Acest cod este contribuit de 29AjayKumar Javascript // Programul Javascript al Selectării rapide // funcție de partiție similară cu sortarea rapidă // Consideră ultimul element ca pivot și adaugă // elemente cu valoare mai mică la stânga și // valoare mare la dreapta și, de asemenea, schimbă // poziția pivot în poziția sa respectivă // în tabloul final.  function _partition(arr, low, high) { let pivot = arr[high], pivotloc = low;   pentru (fie i = scăzut; 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>lungime) { document.write('Index out of bound');  } else { // găsiți a k-a cea mai mică valoare document.write( 'K-a cel mai mic element din matrice: ' + kthSmallest(arraycopy, 0, length - 1, kPosition)+' ');  } // Acest cod este contribuit de rag2127 Ieșire: K-al-lea cel mai mic element este 6 Puncte importante: Ca și quicksort, este rapid în practică, dar are performanță slabă în cazul cel mai rău. Este folosit în Procesul de partiție este același cu QuickSort, numai codul recursiv diferă. Există un algoritm care găsește cel mai mic element al k-lea în O(n) în cel mai rău caz, dar QuickSelect are o performanță mai bună în medie.    Funcția C++ înrudită: std::nth_element în C++