2

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?

hoho97
  • 85
  • 6
  • We do not do homework. We only help with specific problem. Counting sort is bad idea here. I suggest some simple sorting algorithm, like bubble sort. – talex Oct 04 '16 at 15:23
  • 4
    @talex I suppose bubble sort wont run in O(N)... – Gyro Gearless Oct 04 '16 at 15:26
  • Some talk of sorting here: http://stackoverflow.com/questions/4305004/why-arrays-sort-is-quicksort-algorithm-why-not-another-sort-algorithm – Mike Oct 04 '16 at 15:26
  • 3
    @talex it's OK to ask about homework. It's actually irrelevant what the source of the problem is. – weston Oct 04 '16 at 15:27
  • Oh. I didn't notice that constraint. You actually cant implement counting sort for struct in java without extra memory. Even in languages where it possible it will require pretty advanced programming skills. Are you sure you understood your task correct? – talex Oct 04 '16 at 15:29
  • @weston I agree, It is not ok to ask to actually do homework instead of you. – talex Oct 04 '16 at 15:30
  • @talex I don't think they have. They have an idea and are asking if it's correct. – weston Oct 04 '16 at 15:31
  • @weston then I was wrong :) – talex Oct 04 '16 at 15:32
  • I reread the question and realized that I was completely wrong. There is no need in counting sort here. @Jim Garrison provided correct answer – talex Oct 04 '16 at 15:34
  • This is similar to the question that you have an array of 1's and 0's only and you have to put all the 0's to the left of the array `in-place` and in O(n) time – User_Targaryen Oct 05 '16 at 10:35

3 Answers3

8

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.

Jim Garrison
  • 85,615
  • 20
  • 155
  • 190
  • Assuming M – Jim Garrison Oct 04 '16 at 15:38
  • This idea can be expanded even more: Keep a pointer at the last element and one that is traversing the array. Whenever your iterator encounters an element in the wrong position, swap current index with the last index, move last index one step towards the start. Let the iterator check the same index again, then continue towards the "back pointner". when they meat, you are done. – Gikkman Oct 04 '16 at 15:40
  • I thought you meant both pointers were moving together, but I guess you're thinking like this actually: http://stackoverflow.com/a/39856433/360211 – weston Oct 04 '16 at 15:41
  • No I guess I still don't get "wrong section" and how you know whether one is in the wrong section? – weston Oct 04 '16 at 15:43
  • @weston You decide in advance which gender comes first. That determines the order. Also good point about the pointers moving independently, answer updated. – Jim Garrison Oct 04 '16 at 15:45
  • OK, so while looking at one element, how do I know it's in the 'wrong section'? – weston Oct 04 '16 at 15:45
  • OK, so just observing any two: "F???F", you can't tell if they are both correct, but you can know that one is and that lets you move on with that pointer. If both incorrect, swap. – weston Oct 04 '16 at 15:50
  • Full logic for male first sort: "F..F" move right pointer. "M..M" move left pointer. "M..F" move both pointers. "F..M" swap and move both pointers. – weston Oct 04 '16 at 15:52
3

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
Scriptodude
  • 83
  • 7
2

One approach is similar to the partition stage in QuickSort, or to the median/rank finding algorithm QuickSelect.

I'm going to describe the outline of the algorithms, but not provide any code. Hopefully, it will be good enough that it is easy to make the translation.

You basically want to reorganize the array so that one gender is at the start, and the other is at the end of the array. You'll have the array partitioned in three:

  • From 0 to i-1 you have the first gender (male or female, up to you)
  • From i to j-1 you have both male/female. This is the unknown area.
  • From j to n-1 you have the second gender.

At the start of the algorithm i is set to 0, so the first area is empty, and j is set to n-1, so the second area is empty. Basically the whole array is in the unknown state.

Then, you iterate over the array in a particular way. At each step, you look at citizen[i].gender. If it is the first gender, you leave it alone and increment i. If it is the second gender, you swap A[i] with A[j] and decrement j. You stop when i is equal to j.

Why is this correct? Well, at each step we can see that the constraint of having the three areas is maintained, assuming it held to begin with (which it does), and either the first or the second one increases. At the end, the second area has no elements, so we're only left with the first gender at the start, and the second at the end.

Why is it linear? Well, at each step we make a constant-time decision for one element in the array about where it should belong. There's n such elements, so the time is linear in that. Alternatively, the iteration test can be expressed as while (j - i > 0), and the expression j - i starts at n-1 and drops by 1 for each iteration.

Horia Coman
  • 8,681
  • 2
  • 23
  • 25