Kth smallest element algorithm

Question

I'm writing an algorithm that divides and conquers an unsorted array of integers to find the kth smallest element. When testing my program, a couple of my outputs came out wrong. Here is the code:

public class kthsmallest {

public static final int MaxSize = 500;

public static int find_kth_smallest( int[] A, int n, int k )
{
         return quicksort(A, n, k, 0, n-1);
}  

public static int quicksort(int[] A, int n, int k, int low, int high){
int i = low;
int j = high;
int position = low + (high-low)/2;
int pivot = A[position];

while (i <= j){
    while(A[i] < pivot)
        i++;

    while(A[j] > pivot)
        j--;

    if (i <= j){
        int temp = A[i];
        A[i] =A[j];
        A[j] = temp;
        i++;
        j--;
    }
}

//
if (position + 1 > k){
    return quicksort(A, n, k, low, position-1);
} else if (position + 1 < k){
     return quicksort(A, n, k, position+1, high);
} else
    return A[position];

If anyone can see anything wrong with this algorithm, please let me know. I've been debugging for hours. Thanks.

Could you post a data set which produces the wrong solution? — Jason Braucht
– Jason Braucht, Commented Mar 8, 2013 at 18:45

Ivaylo Strandjev · Accepted Answer · 2013-03-08 22:06:35Z

1

You will go wrong for the input 1,2,3,20,4,5,6 and searching for the 6th element. That is because in this case you will have to swap an element more than once and it seems to me you never do that. You will swap 20 and 6 but after that you will increase i and thus will never swap 6 again while you actually should. 6 is the correct answer. I am not sure what value you would find but it will not be 6.

Also several problems may happen because of elements equal to the pivot. Try adding special checks for such elements.

edited Mar 8, 2013 at 22:06

answered Mar 8, 2013 at 21:56

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Kth smallest element algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related