Partitioning an array

Problem
Given a randomly ordered array of n elements, partition the element into two subsets such that element <= x are in one subset and elements >= x are in the other subset.

#include <vector>

int main ( int argc, char **argv) {
	int arr[10] = {28, 26, 25, 11, 16, 12, 24, 29, 6, 10};
	std::vector<int> a(arr, arr + 10); 

	int i  = 0;
	int j  = a.size() - 1;
	int x  = 17;

	while ( (i < j ) && ( a[i] <= x)) i++;
	while ( ( i < j) && ( a[j] > x))  j--;

	if ( a[j] > x )  j--;

	while ( i < j )  {
		std::swap( a[i], a[j]);
		i++;
		j--;

		while (a[i] <= x)
			i++;
		while (a[j] > x)
			j--;

	}
	return 0;
}

Algorithm is taken from the book How to Solve It by Computer
My gitHub repository will have all the code.

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