Ronzii's Blog

Just your average geek's blog

Quick Select

Find the kth smallest element of an array using kth order statistic

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int partition(int a[], int left, int right)
{
    int last = left;
    int key = a[left];
    for(int j=left+1; j<=right; j++)
    {
        if(a[j]<key)
        {
            last++;
            swap(a[last],a[j]);
        }
    }
    swap(a[left],a[last]);
    return last;
}
int findRank(int a[],int left, int right, int rank)
{
    int leftEnd  = partition(a,left,right);
    int leftSize = leftEnd - left + 1;
    if(leftSize==rank+1)
        return a[leftEnd];
    else if(rank<leftSize)
        return findRank(a,left,leftEnd-1,rank);
    else
        return findRank(a,leftEnd+1,right,rank-leftSize);
}
int main()
{
    srand(time(NULL));
    int a[] = {3,4,1,7,8,9,34};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
        cout<<findRank(a,0,n-1,i)<<" ";
    return 0;
}
Advertisements

March 31, 2012 - Posted by | C++ | , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s