CODEWITHSUNDEEP
algorithmquicksort
Roger Zhu
Roger Zhu

Reputation: 65

How to find K smallest values using quick sort

The problem is simple if I sort all the values and pick the fist K values. But it wastes too much time because maybe the smallest K values has been sorted before the whole array is sorted. I think the way to solve this problem is to add a flag in the code, but I can not figure out how to put the flag to judge whether the smallest k values has been sort.

Upvotes: 0

Views: 2141

Answers (2)

Lei Mou
Lei Mou

Reputation: 2582

I think the problem can be solved by finding the kth smallest value. Suppose the signature of the function partition in quicksort is int partition(int* array, int start, int end), here is pseudocode which illustrate the basic idea:

int select(int[] a, int start, int end, int k)
{
    j = partition(a,start,end);

    if( k == j)
        return a[j];
    if( k < j )
        select(a,start,j-1,k);
    if( k > j )
        select(a,j+1,end,k-j);
}

index = select(a, 0, length_of_a, k);

Then a[0...index] is the first k smallest values in array a. You can further sort a[0...index] if you want them sorted.

Upvotes: 2

bhuang3
bhuang3

Reputation: 3633

You can use random selection algorithm to solve this problem with O(n) time. In the end, just return sub-array from 0 to k.

Upvotes: 3

Related Questions