CODEWITHSUNDEEP
c++algorithmquickselect
Mexus94
Mexus94

Reputation: 13

Quick Select Algorithm

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);
}

Upvotes: 0

Views: 2234

Answers (2)

greybeard
greybeard

Reputation: 2497

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

Upvotes: 0

thepace
thepace

Reputation: 2221

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];

Upvotes: 2

Related Questions