how to sort an array without a new array?

Question

I'm working on my homework and there's a question that ask us to sort a struct array

The structcitizen consist of an int id and a boolean gender, where id is randomly generated between 1 to 100, and gender is determined by if id is odd or even, odd=true(male) and even=false(female)

for example a = {33, true}

The question requires me to sort the citizen[] array by gender, it seems very easy but it has the following requirements:

run in linear times O(N)

no new array

only constant extra space can be used

I am thinking about using counting sort but it seems a little bit hard to do it without a new array, is there any suggestion?

Answer 1

Since this is a homework question I'm not going to provide code. The following should be sufficient to get you started.

"Sorting" by gender here really means partitioning into two groups. A general purpose sort cannot be better than O(n*log(n)), but partitioning can be done in O(n) with constant space.

Consider iterating from both ends simultaneously (while loop, two index pointers initialized to first and last elements) looking for elements that are in the "wrong" section. When you find one such element at each end, swap them. Note that the pointers move independently of each other, only when skipping over elements that are already in the right section, and of course immediately after a swap, which is a subcase of "elements already in the right section".

Quit when the index pointers meet somewhere in the middle.

This is not a general purpose sort. You cannot do this for the case where the number of keys is unknown.

Answer 2

Since you only have two values to sort, you could use a kind of swap-counting-sort (I couldn't find any relevant paper on that one). There is room for optimisation on that sort, but that will be your job.

Here is a pseudo-code of that special sort according to your issue :

integer maleIndex = 0   // Current position of males in the array

for i=0 until array.size do
   if array.at(i) is a male then

      // after a while, all female will end up at the end
      // while all male will end up at the beginning
      swap(array.at(maleIndex), array.at(i))
      maleIndex = maleIndex + 1
   end
end