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?

Improve this question
10
  • 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. Commented Oct 4, 2016 at 15:23
  • 4
    @talex I suppose bubble sort wont run in O(N)... Commented Oct 4, 2016 at 15:26
  • Some talk of sorting here: stackoverflow.com/questions/4305004/… Commented Oct 4, 2016 at 15:26
  • 3
    @talex it's OK to ask about homework. It's actually irrelevant what the source of the problem is. Commented Oct 4, 2016 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? Commented Oct 4, 2016 at 15:29

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

Assuming M<F you'll end up swapping first F with second M and you're done.
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.
I thought you meant both pointers were moving together, but I guess you're thinking like this actually: stackoverflow.com/a/39856433/360211
No I guess I still don't get "wrong section" and how you know whether one is in the wrong section?
@weston You decide in advance which gender comes first. That determines the order. Also good point about the pointers moving independently, answer updated.
|
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
Improve this answer

Comments

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.

Improve this answer

1 Comment

minor correction, j-i starts at n-1. ((n-1) - (0)).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.