How to find kth smallest integer in an unsorted array without sorting the array?

Question

So I am given an (unsorted) array A of N distinct integers, I am trying to implement a divide-and-conquer algorithm to find the Kth smallest element (K ≤ N) in the array (i.e. it would be the overall smallest if K=1). The algorithm returns the value of the Kth smallest element in the array. I need it to run in O(N) time in the average case. Could anyone give me some hints?

Answer 1

Sephy, I'm going to walk this through very carefully. You always have to be careful when helping people with algorithms, because, and I cannot stress this enough, solving algorithm problems are to programmers what weight-lifting is to professional athletes. Knowing how to put yourself into the mode of thinking like a computer is what you will get paid to do in a few years. So if the solutions are just given to you, you're going to be the guy that bounces from job to job every 6 months instead of the guy who becomes the lead developer, or goes out on his own with a successful company.

Now that that rant is out of the way...

Traditionally, we think of algorithms that loop through the array once, and loop through it differently based on the first result, and repeat until we met some condition, to be O(n^2). Things that meet this criteria are selection sort, insertion sort, and bubble sort.

But it doesn't have to be. If we can properly divide the array into segments and prove the size of those segments, we can keep it on a low order.

And, with most divide and conquer algorithms, we can start in the middle.

Let A be an array of size N with N distinct elements in it.

Let M be the element that resides at A[N/2]

Let A-large be an array of all elements greater than M.
Let A-small be an array of all elements less than M.

What do we know about A-small and A large? Are they the same size? Maybe, but probably not.

Is size(A-small) > k? or is it < k?

If size(A-small) == k - 1, wouldn't that make M the kth smallest element?

Is there something we can do to create a new value for k and do some recurrsion here?

I'm not going to finish this for you, because there should be plenty to chew on. These are the questions you need to ask yourself. @templatetypedef is 100% on the right track, this is just expanding on it.

If you have some more questions, ask them, but there should be enough here to allow you to solve it without robbing you of your mental exercise.

Answer 2

As a hint, think about how the quicksort partition step works. It splits the input up so that the pivot is in its final position, smallest elements are to the left, and larger elements are to the right. Given this information, and knowing what index you were trying to find, could you think of a way to recursively find the kth element?

Answer 3

import java.util.Scanner;


public class JavaApplication1 {
 public static int findpivot(int a,int b,int c){
     //System.out.println("x");
      if(a > b){
        if(c > a){
            return a;
        }
        else if(c > b){
            return c;
        }
        else{
            return b;
        }
    }
    else{
        if(c > b){
            return b;
        }
        else if(c > a){
            return c;
        }
        else{
            return a;
        }
    }
}

public static void find(int arr[],int l,int r,int target){
    //System.out.println(1);
    if(l >= r){
        return;
    }
    int mid = (l+r)/2;
       // System.out.println(1);
    int pivot = findpivot(arr[mid],arr[l],arr[r]);
    int i = l;
    int j = r;
    while(i<=j){
        while(arr[i] < pivot)i++;
        while(arr[j] > pivot)j--;
        if(i<=j){
            int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;//
            i++;
            j--;
        }

    }
    if(target <= (i-1)){
        find(arr,0,i-1,target);
    }
    else{
        find(arr,i,r,target);
    }
}

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            int arr[] = new int[n];
            for(int i = 0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int k = sc.nextInt();
            find(arr,0,n-1,k-1);
            System.out.println(arr[k-1]);
        }

    }

}

Time Complexcity is almost O(N).

Answer 4

Count the occurrences of each integer in the array in another array.

Answer 5

For such classic problems, wikipedia works very well... See Selection algorithm on wikipedia

Answer 6

Here is my code. This is an O(n) solution. I didn't find anything good online, so I decided to post this here. Hope you find it helpful.

def Smallest(arr, k):
    # # The brute force method
    # if(len(arr)<k):
    #    return 0
    # diff = []
    # for i in range(len(arr)):
    #     for j in range(i+1, len(arr)):
    #         diff.append(abs(arr[i]-arr[j]))
    # sortedDiff = sorted(diff)
    # print(diff)
    # print(sortedDiff)
    # return sortedDiff[k-1]

    #Efficient method
    if(len(arr)<k):
            return 0
    # (i, j, minDiff, count) = (0, 1, arr[1]-arr[0], 0)
    (i, j, minDiff) = (0, 1, [])
    while(i < len(arr)):
        if(j>len(arr)-1):
            i+=1
            if(i==len(arr)-1):
                break
            j=i+1
        else:
            minDiff.append(abs(arr[i]-arr[j]))
            j+=1
    # print(minDiff)
    (minElement, count) = (minDiff[0], 0)
    for i in range(len(minDiff)):
        if(count<k):
            minElement = minDiff[i]
            count+=1
            # print(minElement, count)
            if(count==k):
                return minElement
            else:
                continue
        else:
            # print("This part is being hit")
            continue

Answer 7

try searching for the selection algorithm, or the selection sort algorithm