Finding the kth smallest element

Problem
Given a randomly ordered array of n elements determing the kth smallest element in the set. Overall complexity of this algorithm is O(n)

#include <vector>
#include <iostream>

template < class T>
T kth_smallest( std::vector<T>& a, int k ) {
	int l = 0;
	int u = static_cast<int>(a.size()) - 1;
	while ( l < u ) {
		int i = l; // upper limit of left partition
		int j = u; // lower limit of right partition
		T x   = a[k];
		while(i <= k && j >= k) {
			while( a[i] < x ) 
				i++;			
			while ( x < a[j] ) 
				j--;			
			std::swap(a[i],a[j]);
			i++;
			j--;
		}
		if ( j < k ) 
			l = k;
		if ( i > k )
			u = j;
	}
	return a[k];
}
int main(int argc, char** argv) {
	int arr[10] = {28, 26, 25, 11, 16, 12, 24, 29, 6, 10};
	std::vector<int> my_vec(arr, arr + 10); 
	for ( int i = 0; i < my_vec.size(); i++) 
		std::cout << i << "th smallest element is " << kth_smallest<int> ( my_vec, i ) << std::endl;

	return 0;
}

Same code with minor modification with comparison condition can be used to find the kth largest element

template < class T>
T kth_largest( std::vector<T>& a, int k ) {
	int l = 0;
	int u = static_cast<int>(a.size()) - 1;
	while ( l < u ) {
		int i = l; // upper limit of left partition
		int j = u; // lower limit of right partition
		T x   = a[k];
		while(i <= k && j >= k) {
			while( a[i] > x ) 
				i++;			
			while ( x > a[j] ) 
				j--;			
			std::swap(a[i],a[j]);
			i++;
			j--;
		}
		if ( j < k ) 
			l = k;
		if ( i > k )
			u = j;
	}
	return a[k];
}
Advertisements

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