Dutch flag problem – variation

We are given an array and we need to sort it in the way, so that all negative numbers go to the beginning, all positive numbers to the end and the relative position of numbers is not changed. In example: [-1, 4, 0, -2, 2] => [-1, -2, 0, 4, 2].

Basically I have promised to myself to stop updating this blog for a while, as I am kinda busy recently, but this question surprised me and couldn’t imagine there is a such long discussion related to it.

The problem has been described at careercup.com, and I can’t believe no one has noticed such a simple solution. So basically we are given an array of numbers, where some of them are negative and some of them positive. We need to sort the array in the way, negative numbers go first, positive after, but the relative position is not changed. This means that if we have an array [-1,3,-3,2] the answer should be [-1,-3,3,2]. So what we need is a stable sort. However it would be still not enough. But what if we don’t perceive numbers as numerical values, but we assign them one of three types: positive, null, negative? Then we are done actually.

In the other words, let’s assign all the negative numbers the value -1 and all positive numbers value 1. Let 0 be 0 😉 So we may write a following implementation in c++:

bool cmp(int a, int b)
{
// consider negative numbers as the same class
if(a < 0 && b < 0) return false;
// consider positive numbers as the same class
else if(a > 0 && b > 0) return false;
// otherwise normal comparison will do. This includes
// also the case when a = 0 or b == 0 then we use the normal comparison
else return a < b
}

void special_sort(vector &amp; special_vector)
{
stable_sort(
  special_vector.begin(),
  special_vector_end(),
  cmp);
}

So what we did, we just solved this much discussed problem using nothing more than sorting and STL library to get the complexity of O(n logn) that matches the best solutions from careercup.com 🙂

Best Regards

Joe Kidd

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