クイック選択 は、順序なしリストで k 番目に小さい要素を見つける選択アルゴリズムです。それは、 クイックソート ソートアルゴリズム。
例:

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

アルゴリズムは QuickSort に似ています。違いは、(ピボットを見つけた後) 両側で反復するのではなく、k 番目に小さい要素を含む部分でのみ反復することです。ロジックは単純で、分割された要素のインデックスが k より大きい場合、左側の部分を再帰します。インデックスが k と同じ場合、k 番目に小さい要素が見つかったことになり、戻ります。インデックスが k より小さい場合は、右側の部分を再帰します。これにより、予想される複雑さは O(n log n) から O(n) に減少し、最悪の場合は 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) kthSmallest(arr, l,index - 1, k)を返します。     // それ以外の場合は、右側の部分配列を再帰します return kthSmallest(arr, Index + 1, r, k - Index + l - 1);   } // k が配列内の要素数より大きい場合 // return INT_MAX;  } // 上記のメソッドをテストするドライバー プログラム int main() { int arr[] = { 10, 4, 5, 8, 6, 11, 26 };   int n = sizeof(arr) / sizeof(arr[0]);   int k = 3;   コート<< '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('範囲外のインデックス');   } else { // k 番目の最小値を検索 System.out.println( '配列内の K 番目の最小要素 : ' + kthSmallest(arraycopy, 0, length - 1, kPosition));   } } } // このコードは、Saiteja Pamulapati によって寄稿されました。 Python3 # QuickSelect の Python3 プログラム # QuickSort() の標準パーティション プロセス。  # 最後の要素をピボットと見なします # 小さい要素をすべて左側に移動し、大きい要素を右側に移動します def Partition(arr, l, r): x = arr[r] i = l for j in range(l, r): 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と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) # それ以外の場合は、右側の部分配列を再帰します return kthSmallest(arr, Index + 1, r, k - Index + l - 1) print('Index out of bound') # ドライバー コード arr = [ 10, 4, 5, 8, 6, 11, 26 ] n = len(arr) k = 3 print('K 番目に小さい要素は ', end = ' ') print(kthSmallest(arr, 0, n - 1, k)) # このコードは Muskan Kalra によって提供されました。   C# // システムを使用したクイック選択の C# プログラム;    class GFG { // クイック ソートに似たパーティション関数 // 最後の要素をピボットとみなして、 // 値の小さい要素を左側に、 // 値の大きい要素を右側に追加し、 // ピボット位置をそれぞれの位置に変更します // / 読み取り専用配列内。   static int Partitions(int []arr,int low, int high) { int pivot = arr[high], pivotloc = low, temp;   for (int i = low; 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('範囲外のインデックス');   } else { // k 番目の最小値を検索 Console.WriteLine('配列内の K 番目の最小要素 : ' + kthSmallest(arraycopy, 0, length - 1, kPosition - 1));   } } } // このコードは 29AjayKumar によって提供されています Javascript // クイック選択の Javascript プログラム // クイック ソートと同様のパーティション関数 // 最後の要素をピボットと見なし、 // 値が小さい要素を左側に追加し、 // 値が大きい要素を追加します// また、ピボット位置を、 // 最終配列内のそれぞれの位置に変更します。  function _partition(arr, low, high) { let pivot = arr[high], pivotloc = low;   for (let i = low; 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('インデックスが範囲外です ');  } else { // k 番目の最小値を見つける document.write( '配列内の K 番目の最小要素 : ' + kthSmallest(arraycopy, 0, length - 1, kPosition)+' ');  } // このコードは rag2127 によって提供されています 出力: K 番目の最小要素は 6 重要なポイント: クイックソートと同様に、実際には高速ですが、最悪の場合のパフォーマンスが低くなります。パーティション処理は QuickSort と同じですが、再帰コードのみが異なります。最悪の場合に O(n) 内の k 番目に小さい要素を見つけるアルゴリズムが存在しますが、平均すると QuickSelect の方がパフォーマンスが優れています。    関連する C++ 関数 : C++ の std::nth_element>>