Quickselect er en udvælgelsesalgoritme til at finde det k-te mindste element i en uordnet liste. Det er relateret til hurtig 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 QuickSort. Forskellen er, at den i stedet for at gå igen for begge sider (efter at have fundet pivot), kun gentager sig for den del, der indeholder det k-te mindste element. Logikken er enkel, hvis indekset for det partitionerede element er mere end k, så går vi igen for den venstre del. Hvis indeks er det samme som k, har vi fundet det k-te mindste element, og vi vender tilbage. Hvis indeks er mindre end k, så går vi igen for den rigtige del. Dette reducerer den forventede kompleksitet fra O(n log n) til O(n), med et værste tilfælde af 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 mere end antallet af // elementer i array returnerer INT_MAX;  } // Driverprogram til at teste ovenstå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>længde) { System.out.println('Indeks uden for grænsen');   } else { // find kth mindste værdi System.out.println( 'K-th mindste element i array : ' + kthSmallest(arraycopy, 0, længde - 1, kPosition));   } } } // Denne kode er bidraget af Saiteja Pamulapati Python3 # Python3-programmet fra Quick Select # Standard partitionsprocessen for QuickSort().  # Den betragter det sidste element som pivot # og flytter alle mindre elementer til venstre for # it og større elementer til højre def partition(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, index - 1, k) # Ellers gentages for højre subarray returnerer kthSmallest(arr, index + 1, r, k - index + l - 1) print('Indeks ud af bundet') # Driverkode arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K-te mindste element er ', ende = ' ') print(kthSmallest(arr, 0, n - 1, k)) # Denne kode er bidraget af Muskan Kalra.   C# // C#-program for Quick Select ved hjælp af System;    klasse GFG { // partitionsfunktion svarende til hurtig sortering // Betragter sidste element som pivot og tilføjer // elementer med mindre værdi til venstre og // høj værdi til højre og ændrer også // pivotpositionen til sin respektive position / / i det skrivebeskyttede array.   statiske int partitioner(int []arr,int lav, int høj) { int pivot = arr[høj], 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 uden for grænsen');   } else { // find kth mindste værdi Console.WriteLine('K-th mindste element i array : ' + kthSmallest(arraycopy, 0, længde - 1, kPosition - 1));   } } } // Denne kode er bidraget af 29AjayKumar Javascript // Javascript-program med Quick Select // partitionsfunktion svarende til hurtig sortering // Betragter sidste element som pivot og tilføjer // elementer med mindre værdi til venstre og // høj værdi til højre og ændrer også // pivotpositionen til dens respektive position // i det endelige array.  funktion _partition(arr, lav, høj) { lad pivot = arr[høj], pivotloc = lav;   for (lad 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 uden for bundet ');  } else { // find kth mindste værdi document.write( 'K-th mindste element i array : ' + kthSmallest(arraycopy, 0, længde - 1, kPosition)+' ');  } // Denne kode er bidraget af rag2127 Output: K-te mindste element er 6 vigtige point: Ligesom quicksort er det hurtigt i praksis, men har dårlig værst tænkelig ydeevne. Det bruges i Partitionsprocessen er den samme som QuickSort, kun den rekursive kode er forskellig. Der findes en algoritme, der finder k-te mindste element i O(n) i værste tilfælde, men QuickSelect klarer sig bedre i gennemsnit.    Relateret C++ funktion: std::nth_element i C++>