kth_smallest.cpp

Kth Largest element in an array in time O(n) without sorting the entire array.

// kth_smallest.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <iostream>
using namespace std;
inline int swap(int arr[],int i,int j)
{
    int temp=arr[i];arr[i]=arr[j];arr[j]=temp;
    return 0;
}
int rand_part(int arr[],int min,int max)
{
    int pivot=arr[min],i=min,j=i+1;
    for(;j<=max;j++)
    {
        if(arr[j]<pivot)
        {
            i=i+1;
            swap(arr,i,j);
        }
    }
    swap(arr,min,i);
return i;
}

int rand_select(int *arr,int p,int q,int i)
{
	if(p==q)
		return arr[p];
	int r=rand_part(arr,p,q);
	int k=r-p+1;
	if(i==k)
		return arr[r];
	if(i<k)
		return rand_select(arr,p,r-1,i);
	else
		return rand_select(arr,r+1,q,i-k);
	return 0;
}
int main()
{
	int n,*arr,k;
	cout<<"\n\nKth Smallest Element :"<<endl;
	cout<<"\n\nEnter the number of elements in the array :"<<endl;
	cin>>n;
	arr=new int[n];
	cout<<"\nEnter the elements of the array :"<<endl;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	cout<<"\nEnter the value of \"K\" :";
	cin>>k;
	cout<<"\n\n"<<k;
		cout<<"th ";
	cout<<"Smallest Element is :";
	cout<<rand_select(arr,0,n-1,k)<<endl;
	return 0;
}