hoho97 - 1 year ago 70

Java Question

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

The struct

`citizen`

`int id`

`boolean gender`

`id`

and

`gender`

`id`

`true`

`false`

for example

`a = {33, true}`

The question requires me to sort the

`citizen[]`

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 Source

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`

and drops by `1`

for each iteration.