CODEWITHSUNDEEP
c++arraysalgorithmrecursionpartition
user16666322
user16666322

Reputation: 135

Recursively obtaining kth smallest element in an array

I'm trying to "translate" this algorithm from the pseudocode provided in my textbook. My program keeps crashing though, and I'm not really sure where I went wrong with my implementation. Here's the pseudocode in image with my code right below it: enter image description here

int kSmallFirst (int k, int anArray[], int first, int last) {
    int pivotIndex = 0;

    if (k < pivotIndex - first + 1)
        return kSmallFirst(k, anArray, first, pivotIndex - 1);
    else if (k == pivotIndex - first + 1)
        return pivotIndex;
    else
        return kSmallFirst(k - (pivotIndex - first + 1), anArray, pivotIndex + 1, last);
}

int main () {
    int i = 0;
    int arr[512];
    fstream data;
    data.open("data.txt");

    while (!data.eof()) {
        data >> arr[i];
        i++;
    }

    data.close();

    cout << kSmallFirst(42, arr, 0, i-1);

    return 0;
}

Thank you very much!

Upvotes: 0

Views: 4542

Answers (3)

CiaPan
CiaPan

Reputation: 9570

The problem is: you have not implemented the main part of the algorithm, which is described in your book with italic font:

Choose a pivot value 'p' form 'anArray[first..last]'

Partition the values of 'anArray[first..last]' about 'p'

These two lines are not a comment! They are the pseudocode you're going to translate to C/C++ to make your code to do what you want it to do.

Upvotes: 4

Jonathan Mee
Jonathan Mee

Reputation: 38919

Note that kSmallFirst never uses anArray, so contrary to what JoriO says this is not an input problem. Even if it did try to use a range main is passing the range [0 .. -1] in as kSmallFirst's first and last.

You need to understand what the algorithm is doing, otherwise as is mentioned by CiaPan you won't implement the most important part.

kSmall is:

  1. Taking in a partition of anArray defined by first and last
  2. Choosing a pivotIndex in the partition of anArray between first and last
  3. Moving all elements smaller than anArray[pivotIndex] below pivotIndex and all elements larger than anArray[pivotIndex] above pivotIndex
  4. This will define the next pair of partitions of anArray, the partition from first to pivotIndex and the partition from pivotIndex to last
  5. kSmall will recurse on the range that will contain the kth element

Rewriting kSmall with this in mind will yield:

#include <algorithm>
#include <functional>

int kSmall(int k, int* anArray, int first, int last){
    int p = anArray[(last - first) / 2 + first]; // Choose a pivot value from anArray[first .. last]
    int* pivotIndex = std::partition(anArray + first, anArray + last, std::bind2nd(std::less<int>(), p)); // Partition the values of anArray around p

    if(k < pivotIndex - anArray){
        return kSmall(k, anArray, first, pivotIndex - anArray);
    }
    else if(k == pivotIndex - anArray){
        return pivotIndex - anArray;
    }
    else{
        return kSmall(k, anArray, pivotIndex - anArray, last);
    }
}

I'm sure you'll notice that the math in the if statement differs from the book. I've chosen to implement kSmall, as you did using int parameters, the book chose to use int* parameters.

Upvotes: 2

Gopichand
Gopichand

Reputation: 1016

You choice of pivot index value is wrong.

Since this is a recursion you need to update your pivot for every call.

Make it more generic.

In the kSmallFirst function,

Use pivotIndex = first, rather than pivotIndex = 0.

Upvotes: 0

Related Questions