Help me implementing ksmall as a function

[zekkragnos]

Implement ksmall as a C++ function. Use the first item of the array as the pivot. This is what I have so far, but everytime I compile it crashes :(

#include <cstdlib>
#include <iostream>

using namespace std;

int kSmall(int k, int anArray[], int first, int last);

int main()
{
    int anArray[8]={4,7,3,6,8,1,9,2};
    
    int first = 0;
    int last = 7;
    int k = anArray[first];
    int m = kSmall(k,anArray,first,last);
    cout<<m;
    
    system("PAUSE");
    return 0;
}

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

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

[abhishekm71]

Its not clear what the program is trying to accomplish. Please clarify.

[tath]

for me it seems like, he brainlessly modified this program http://harvestsoft.net/files/kthsmallest.pdf.

[zekkragnos]

The programming problem asks the reader to implement the function kSmall(k, anArray, first, last).

The recursive definition is as follows:

= kSmall(k, anArray, first, pivotIndex - 1)
if k < pivotIndex - first + 1

= p
if k = pivotIndex - first + 1

= kSmall(k - (pivotIndex - first + 1), anArray, pivotIndex + 1, L)
if k > pivotIndex - first + 1

My issue is how to partition the array correctly. The book tells the reader to just use the first item in the array for your pivot because it has not discussed how to choose the pivot so that it maximizes the algorithm.

[abhishekm71]

i'm sorry it is still not clear to me what the program is supposed to do.