Hurtigvalg er en utvalgsalgoritme for å finne det k-te minste elementet i en uordnet liste. Det er relatert til rask sortering sorteringsalgoritme.
Eksempler:

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 ligner på QuickSort. Forskjellen er at i stedet for å gjenta seg for begge sider (etter å ha funnet pivot), gjentar den seg bare for den delen som inneholder det k-te minste elementet. Logikken er enkel, hvis indeksen til det partisjonerte elementet er mer enn k, går vi tilbake for venstre del. Hvis indeks er det samme som k, har vi funnet det k-te minste elementet og returnerer. Hvis indeksen er mindre enn k, går vi tilbake for høyre del. Dette reduserer den forventede kompleksiteten fra O(n log n) til O(n), med et verste tilfelle 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) returner kthSmallest(arr, l, indeks - 1, k);     // Else recur for right subarray return kthSmallest(arr, index + 1, r, k - index + l - 1);   } // Hvis k er mer enn antall //-elementer i array returnerer INT_MAX;  } // Driverprogram for å teste metodene ovenfor int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 };   int n = størrelse på(arr) / størrelse på(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>lengde) { System.out.println('Indeks utenfor grensen');   } else { // finn kth minste verdi System.out.println( 'K-th minste element i array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // Denne koden er bidratt av Saiteja Pamulapati Python3 # Python3-programmet til Quick Select # Standard partisjonsprosess til QuickSort().  # Den betrakter det siste elementet som pivot # og flytter alle mindre elementer til venstre for # it og større elementer til høyre def partisjon(arr, l, r): x = arr[r] i = l for j i område(l, r): hvis 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 og 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): returner kthSmallest(arr, l, indeks - 1, k) # Else recur for right subarray return kthSmallest(arr, index + 1, r, k - index + l - 1) print('Indeks ut av bundet') # Driverkode arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-te minste element er ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Denne koden er bidratt av Muskan Kalra.   C# // C#-programmet til Quick Select ved hjelp av System;    klasse GFG { // partisjonsfunksjon som ligner på hurtigsortering // Betrakter siste element som pivot og legger til // elementer med mindre verdi til venstre og // høy verdi til høyre og endrer også // pivotposisjonen til sin respektive posisjon / / i den skrivebeskyttede matrisen.   statiske int partisjoner(int []arr,int lav, int høy) { int pivot = arr[høy], pivotloc = lav, temp;   for (int i = lav; 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('Indeks utenfor grensen');   } else { // finn kth minste verdi Console.WriteLine('K-th minste element i array : ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // Denne koden er bidratt av 29AjayKumar Javascript // Javascript-programmet til Quick Select // partisjonsfunksjon som ligner på hurtigsortering // Betrakter siste element som pivot og legger til // elementer med mindre verdi til venstre og // høy verdi til høyre og endrer også // pivotposisjonen til sin respektive posisjon // i den endelige matrisen.  funksjon _partisjon(arr, lav, høy) { la pivot = arr[høy], pivotloc = lav;   for (la i = lav; 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('Indeks utenom binding ');  } else { // finn kth minste verdi document.write( 'K-th minste element i array : ' + kthSmallest(arraycopy, 0, lengde - 1, kPosition)+' ');  } // Denne koden er bidratt av rag2127 Utgang: K-te minste element er 6 viktige poeng: I likhet med quicksort er det raskt i praksis, men har dårlige worst-case ytelse. Den brukes i Partisjonsprosessen er den samme som QuickSort, bare rekursiv kode er forskjellig. Det finnes en algoritme som finner k-te minste element i O(n) i verste fall, men QuickSelect gir bedre resultater i gjennomsnitt.    Relatert C++-funksjon: std::nth_element i C++