CODEWITHSUNDEEP
c++arraysalgorithmsorting
Nick
Nick

Reputation: 95

C++ sorting array of true false

I have been assigned two similar tasks which should be pretty easy but I need a clarification on what I can and can't do with c++.

Task 1: Suppose you have an array of n elements containing only two distinct keys, true and false. Give an O(n) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.

For task two I need to do the same thing but now there is an extra key "maybe". So i need to sort the array so false precedes maybe and maybe precedes true in O(n).

I am deciding to use insertion sort on the first task and quick sort on the second. My first question is whether or not it is ideal to create an array and sort it with values true false and/or maybe. In my opinion I would want to fist change all the values of false, true and maybe to 0,1,2 and sort the array by numerical values in ascending order. I would do this by first going through the array and changing the values then sorting after. What would be the best way to change the values (if even needed). Would this keep the algorithm in O(n) time?

Thanks for the help!

Upvotes: 1

Views: 2235

Answers (5)

Phil1970
Phil1970

Reputation: 2624

From the start, find the first ˋtrueˋ element. From then end, find the first ˋfalseˋ element. Swap them and repeat for remaining elements until both iterators are equals. O(n) for data with 2 states.

For 3 states, I would do someting similar but use extra 2 extra iterators to remember from where I got ˋmaybeˋ.

I am not sure if it would also works with 4 items. It might be greater than O(n) since some items migh be exanged twice!

Upvotes: 0

nneonneo
nneonneo

Reputation: 179677

There's a classic sorting algorithm that runs in O(n) time called the counting sort. More precisely, it runs in O(n+k) time and uses O(k) space, where k is the number of possible keys.

Here, you have only 3 possible keys, true maybe, and false, so k=3. Because this is a constant, it is eliminated in big-O notation, so you get O(n) running time and O(1) space.

Upvotes: 8

Potatoswatter
Potatoswatter

Reputation: 137910

The question is phrased somewhat like homework, but in the real world, std::partition is the right tool for the job.

There's also stable_partition which is slower but preserves ordering, and partition_copy which is O(N) and stable but takes extra space by making a copy.

For the second task, just call partition twice, once to separate false from maybe and true and another time to separate maybe from true. The total cost is still O(N).

Upvotes: 2

Kevin Hsu
Kevin Hsu

Reputation: 1756

Loop through the array and count the number of true values. That is all you need to do. The number of false values is the array_size - #true. This is essentially the same information as the sorted array.

If, for some reason, you need it unpacked (e.g. you need a bitmap for drawing purposes), just memset #false in the array to false, and memset the rest of the array to true (or, vice versa).

Upvotes: 0

3yakuya
3yakuya

Reputation: 2672

For 1.: implement a kind-of counting sort: go through your table counting only 'false' elements. Then write a counted number of false elements to your array and fill the rest of the array with true values.

For 2.: same as for 1., but this time count both false and maybe. Then fill your array just like in 1.

Upvotes: 2

Related Questions