Implementing quickselect

Question

I'm trying to implement the quickselect algorithm. Though, I have understood the theory behind it very well; I'm finding it difficult to convert it into a well functioning program.

Here is how I'm going step by step to implement it and where I am facing problem:

Problem: Find the 4th smallest element in A[] = {2,1,3,7,5,4,6}

k = 4.

index:0|1|2|3|4|5|6

Corresponding values: 2|1|3|7|5|4|6

initially, l = 0 and r = 6

Step 1) Taking pivot as the leftmost element (pivot will always be the leftmost in this problem)-

pivot_index = 0

pivot_value = 2

Step 2) Applying the partition algo; putting the pivot at the right place ([<p][p][>p])-

We get the following array: 1|2|3|7|5|4|6

where, pivot_index = i-1 = 1

and therefore, pivot_value = 2

Step 3) Compare pivot_index with k-

k=3, pivot_index = 1; k>pivot_index

Hence, Our k-th smallest number lies in the right part of the array.

Right array = i to r and we do not bother with the left part (l to i-1) anymore.

Step 4) We modify the value of k as k - (pivot_index) => 4-1 = 2; k = 3.

Here is the problem: Should not the value of k be 2? Because we have two values on the left part of the array: 1|2? Should we calculate k as k - (pivot_index+1)?

Let's assume k = 3 is correct.

Step 5) "New" array to work on: 3|7|5|4|6 with corresponding indexes: 2|3|4|5|6

Now, pivot_index = 2 and pivot_index = 3

Step 6) Applying partition algo on the above array-

3|7|5|4|6 (array remains unchanged as pivot itself is the lowest value). i = 3

pivot_index = i-1 = 2 pivot_value = 3

Step 7) Compare pivot_index with k

k=3 and pivot_index=2

k > pivot_index

and so on....

Is this approach correct?

Here is my code which is not working. I have used a random number generator to select a random pivot, the pivot is then swapped with the first element in the array.

#include<stdio.h>
#include<stdlib.h>

void print_array(int arr[], int array_length){

    int i;

    for(i=0; i<array_length; ++i) {
        printf("%d ", arr[i]);
    }

}

int random_no(min, max){

    int diff = max-min;
    return (int) (((double)(diff+1)/RAND_MAX) * rand() + min);

}

void swap(int *a, int *b){

    int temp; 

    temp = *a;
    *a = *b;
    *b = temp;
}

int get_kth_small(int arr[], int k, int l, int r){

    if((r-l) >= 1){

        k = k + (l-1); 

        int pivot_index = random_no(l, r);

        int i, j;
        swap(&arr[pivot_index], &arr[l]);           //Switch the pivot with the first element in the array. Now, the pivit is in arr[l]

        i=l+1;

        for(j=l+1; j<=r; ++j){
            if(arr[j]<arr[l]){
                swap(&arr[j], &arr[i]);
                ++i;
            }
        }

        swap(&arr[l], &arr[i-1]);                   //Switch the pivot to the correct place; <p, p, >p

        printf("value of i-1: %d\n", i-1);
        printf("Value of k: %d\n", k);

        if(k == (i-1)){
            printf("Found: %d\n", arr[i]);
            return 0;
        }

        if(k>(i-1)){
            k=k-(i-1);
            get_kth_small(arr, k, i, r);
        } else {
            get_kth_small(arr, k, l, r-1);
        }

        //get_kth_small(arr, k, i, r);
        //get_kth_small(arr, k, l, i-1);

    }

}

void main(){

    srand(time(NULL));

    int arr[] = {2,1,3,7,5,4,6};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    int k = 3, l = 0;
    int r = arr_size - 1;

    //printf("Enter the value of k: ");
    //scanf("%d", &k);

    get_kth_small(arr, k, l, r);

    print_array(arr, arr_size);
    printf("\n");

}

Answer 1

What you describe is a valid way to implement quick select. There are numerous other approaches how to select the pivot and most of them will give a better expected complexity but in essence the algorithm is the same.

Answer 2

"Step 2: putting the pivot at the right place": don't do that. In fact you can't put the pivot at the right place, as you don't know what it is. The partitioning rule is to put all elements smaller or equal than the pivot before those larger. Just leave the pivot where it is!

Quick select goes as follows: to find the Kth among N elements, 1) choose a pivot value, 2) move all elements smaller or equal to the pivot before the others, forming two zones of length Nle and Ngt, 3) recurse on the relevant zone with (K, Nle) or (K-Nle, Ngt), until N=1.

Actually, any value can be taken for the pivot, even one not present in the array; but the partition must be such that Nle and Ngt are nonzero.