Snabbval är en urvalsalgoritm för att hitta det k:te minsta elementet i en oordnad lista. Det är relaterat till snabb sortering sorteringsalgoritm.
Exempel:

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

Algoritmen liknar QuickSort. Skillnaden är, istället för att återkomma för båda sidor (efter att ha hittat pivot), återkommer den endast för den del som innehåller det k:te minsta elementet. Logiken är enkel, om indexet för det partitionerade elementet är mer än k, så återkommer vi för den vänstra delen. Om index är detsamma som k, har vi hittat det k:te minsta elementet och vi returnerar. Om index är mindre än k, så återkommer vi för den högra delen. Detta minskar den förväntade komplexiteten från O(n log n) till O(n), med ett värsta fall av 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) returnera kthSmallest(arr, l, index - 1, k);     // Else recur for right subarray return kthSmallest(arr, index + 1, r, k - index + l - 1);   } // Om k är fler än antalet // element i array returnerar INT_MAX;  } // Drivrutinsprogram för att testa ovanstående metoder 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>length) { System.out.println('Index out of bound');   } else { // hitta kth minsta värde System.out.println( 'K-th minsta element i array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // Den här koden är bidragit från Saiteja Pamulapati Python3 # Python3-programmet för Quick Select # Standardpartitionsprocessen för QuickSort().  # Den betraktar det sista elementet som pivot # och flyttar alla mindre element till vänster om # it och större element till höger def partition(arr, l, r): x = arr[r] i = l för j i range(l, r): om 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 och 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): returnera kthSmallest(arr, l, index - 1, k) # Annars återkommer för höger subarray return kthSmallest(arr, index + 1, r, k - index + l - 1) print('Index out of bunden') # Driver Code arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-te minsta elementet är ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Den här koden är bidragit av Muskan Kalra.   C# // C#-programmet för Quick Select med System;    class GFG { // partitionsfunktion som liknar snabb sortering // Betraktar det sista elementet som pivot och lägger till // element med mindre värde till vänster och // högt värde till höger och ändrar även // pivotpositionen till sin respektive position / / i den skrivskyddade matrisen.   statiska int partitioner(int []arr,int låg, int hög) { int pivot = arr[hög], pivotloc = låg, temp;   för (int i = låg; 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>length) { Console.WriteLine('Index out of bound');   } else { // hitta kth minsta värde Console.WriteLine('K-th minsta element i array: ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // Den här koden är bidragit av 29AjayKumar Javascript // Javascript-programmet för Quick Select // partitionsfunktion som liknar snabbsortering // Betraktar det sista elementet som pivot och lägger till // element med mindre värde till vänster och // högt värde till höger och ändrar också // pivotpositionen till sin respektive position // i den slutliga arrayen.  function _partition(arr, low, high) { let pivot = arr[high], pivotloc = low;   för (låt i = låg; 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>length) { document.write('Index out of bound ');  } else { // hitta kth minsta värde document.write( 'K-th minsta element i array : ' + kthSmallest(arraycopy, 0, längd - 1, kPosition)+' ');  } // Denna kod bidrar med rag2127 Utdata: K-te minsta elementet är 6 Viktiga poäng: Liksom quicksort är det snabbt i praktiken, men har dålig prestanda i värsta fall. Det används i Partitionsprocessen är samma som QuickSort, endast rekursiv kod skiljer sig. Det finns en algoritm som hittar k:te minsta elementet i O(n) i värsta fall, men QuickSelect presterar bättre i genomsnitt.    Relaterad C++-funktion: std::nth_element i C++>