CODEWITHSUNDEEP
calgorithmrecursion
JavascriptLoser
JavascriptLoser

Reputation: 1962

Implementation of the quick select algorithm to find kth smallest number

I'm currently working on a program to find the kth smallest number of an array using the quick select algorithm. I've finished it and it works but does not give the correct result every time.

Here's my code (I didn't include my partition or swap algorithm, I'm fairly sure they're correct):

/*
inputs...
*A: pointer to array
n: size of array
k: the item in question
*/
int ksmallest(int *A, int n, int k){

    int left = 0; 
    int right = n - 1; 
    int next = 1;

    return quickselect(A, left, right, k);
}

int quickselect(int *A, int left, int right, int k){

    //p is position of pivot in the partitioned array
    int p = partition(A, left, right);

    //k equals pivot got lucky
    if (p - 1 == k - 1){
        return A[p];
    }
    //k less than pivot
    else if (k - 1 < p - 1){
        return quickselect(A, left, p - 1, k);
    }
    //k greater than pivot
    else{
        return quickselect(A, p + 1, right, k);
    }
}

Everything compiles fine. I then tried to use the program on the following array: [1,3,8,2,4,9,7]

These were my results:

> kthsm 2
4
> kthsm 1
1
> kthsm 3
2

As you can see, it worked correctly on the 1th smallest item, but failed on the others. What could be the problem? I guessed than my indexing was off but I'm not exactly sure.

EDIT: Added my partition and swap code below, as requested:

int partition(int *A, int left, int right){

    int pivot = A[right], i = left, x;

    for (x = left; x < right - 1; x++){
        if (A[x] <= pivot){
            swap(&A[i], &A[x]);
            i++;
        }
    }

    swap(&A[i], &A[right]);
    return i;
}

//Swaps
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

Upvotes: 4

Views: 9351

Answers (1)

ilim
ilim

Reputation: 4547

In your partition function the loop condition should be x < right, not x < right - 1.

Also, in the if statements in quickselect, you should switch both uses of p-1 to p. p is already an index and by decreasing k by 1 you turn it into an index(rather than an order) as well. There is no need to decrease p by one again.

int partition(int *A, int left, int right){
    int pivot = A[right], i = left, x;
 
    for (x = left; x < right; x++){
        if (A[x] < pivot){
            swap(&A[i], &A[x]);
            i++;
        }
    }
 
    swap(&A[i], &A[right]);
    return i;
}
 
 
int quickselect(int *A, int left, int right, int k){
 
    //p is position of pivot in the partitioned array
    int p = partition(A, left, right);
 
    //k equals pivot got lucky
    if (p == k-1){
        return A[p];
    }
    //k less than pivot
    else if (k - 1 < p){
        return quickselect(A, left, p - 1, k);
    }
    //k greater than pivot
    else{
        return quickselect(A, p + 1, right, k);
    }
}

Here's a working example. http://ideone.com/Bkaglb

Upvotes: 6

Related Questions