Selection Procedure Algorithm - CSU083 - Shoolini U

Selection Procedure (Quick Select)

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