Quick Select Algorithm

Question

I'm trying to implement the Quick Select Algorithm on an array that has randomly generated numbers. Now after coding the algorithm, it does not sort the array from lowest to highest nor am I able to find the kth smallest element.

#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;

int Partition(int *myArray, int startingIndex, int endingIndex){
    int pivot = myArray[endingIndex];
    int partitionIndex = startingIndex;
    for(int i = startingIndex; i<endingIndex; i++){
        if(myArray[i]<= pivot){
            swap(myArray[i],myArray[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(myArray[partitionIndex],myArray[endingIndex]);
    return partitionIndex;
} 
 
int QuickSelect(int *myArray, int startingIndex, int endingIndex, int KthElement){
    if (startingIndex < endingIndex){
        int partitionIndex = Partition(myArray, startingIndex, endingIndex);
        if(KthElement == partitionIndex)
            return KthElement;
        if(KthElement < partitionIndex)
            QuickSelect(myArray, startingIndex, partitionIndex - 1, KthElement);
        else
            QuickSelect(myArray, partitionIndex + 1, endingIndex, KthElement);
    }
}
    /*if(startingIndex < endingIndex){
        int partitionIndex = Partition(myArray, startingIndex,endingIndex);
        QuickSelect(myArray,startingIndex,partitionIndex-1);
        QuickSelect(myArray,partitionIndex+1,endingIndex);
    }// 1 */

void printArray(string intro, int const *myArray, int n, ostream &out) {
    out << intro;
    for(int i = 0; i < n; i++){
        out << " " << myArray[i];
    }
    out << endl;
}

int main(){
    int numOfElements;
    int KthElement;
    srand(time(NULL));
    cout<<"Enter The Amount Of Numbers You Wish To Use: ";
    cin >> numOfElements;
    int myArray[numOfElements];

    for(int i = 0; i< numOfElements; i++){
        myArray[i] = rand() %10;
    }

    printArray("Array Before Sorting:", myArray, numOfElements, cout);

    cout <<"\nEnter The Rank K Of The Element You Wish To Retrieve: ";
    cin >> KthElement;

    QuickSelect(myArray,0,numOfElements,KthElement);

    printArray("Array After Sorting:", myArray, numOfElements, cout);

    cout << "The " << KthElement << " Smallest Element Is: "
         << QuickSelect(myArray,0,numOfElements,KthElement);
}

Just a small reminder, the quick select algorithm will NOT sort your array. — iForests, Jan 07 '15 at 07:46
The QuickSelect algorithm does not sort the entire array. That's not what it's for. That's how it differs from QuickSort, which does. — user207421, Aug 06 '23 at 07:51

thepace · Answer 1 · 2015-01-07T16:00:17.737

For numOfElements as 5, array extends from 0 to 4. Your endingIndex assumes that its the last index of the array.

Fix:

QuickSelect(myArray, 0,numOfElements-1,KthElement);

Problems with your code:

Your program accesses out of bound array locations in
```
int pivot = myArray[endingIndex];
```
Have a check for k<1 and k>(num_of_elements).
Check your code for num_of_elements = 1 as well.
Check what k means for the array, i.e For k=1 , arr[0] should be returned not arr[1];

score 0 · Answer 2 · answered Aug 06 '23 at 07:57

0

Problems with your int QuickSelect():
• not documented - what does it return, why KthElement and not k?
• does not always return a value
• where it does return a value, it is always the unmodified value of its last parameter

answered Aug 06 '23 at 07:57

greybeard

2,249
8
30
66

Quick Select Algorithm

2 Answers2

Linked