Introduction
This is an introduction of Quick Select, also known as Selection Procedure, Algorithm.
Language: C++
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
// Function to swap two elements in the array
void swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to partition the array and return the pivot index
int partition(int arr[], int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr, i, storeIndex);
storeIndex++;
}
}
swap(arr, storeIndex, right);
return storeIndex;
}
// Function for Quick Select algorithm
int quickSelect(int arr[], int left, int right, int k) {
if (left == right)
return arr[left];
int pivotIndex = left + rand() % (right - left + 1);
pivotIndex = partition(arr, left, right, pivotIndex);
if (k == pivotIndex)
return arr[k];
else if (k < pivotIndex)
return quickSelect(arr, left, pivotIndex - 1, k);
else
return quickSelect(arr, pivotIndex + 1, right, k);
}
int main() {
int n;
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
cout << "Enter " << n << " elements: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int k;
cout << "Enter the value of k for the kth smallest element: ";
cin >> k;
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// Seed the random number generator
srand(time(NULL));
int result = quickSelect(arr, 0, n - 1, k - 1); // k - 1 to find kth smallest element (0-based indexing)
cout << "The " << k << "th smallest element is: " << result << endl;
return 0;
}
Output:
Enter the number of elements in the array: 5
Enter 5 elements: 1 10 7 11 2
Enter the value of k for the kth smallest element: 2
Original array: 1 10 7 11 2
The 2th smallest element is: 2