1

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!

6
  • Inertion sort is not O(n) everytime...
    – deviantfan
    Apr 18, 2014 at 18:16
  • The O(n) requirement is incompatible with your decision to use insertion sort. You need to change the requirement. ;-) Apr 18, 2014 at 18:17
  • 2
    For T/F: There are only two possible values. Iterate through once and count them. Iterate through a second time and set your ordering (do your sort).
    – Tawnos
    Apr 18, 2014 at 18:17
  • What would be O(n)? It seems like this is what my instructor was looking for when asking this question.
    – Nick
    Apr 18, 2014 at 18:18
  • Still need to know if it is possible to compare True and False.
    – Nick
    Apr 18, 2014 at 18:19

5 Answers 5

8

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.

1
2

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.

2

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).

9
  • When the question asks for specific time and space requirements, I don't think just mentioning a standard function with no explanation as to how it works is useful as an answer. Not to mention that it isn't clear what the space complexity of this function is from the answer or the given link. Apr 18, 2014 at 18:23
  • 1
    @Dukeling std::partition is O(N) or this wouldn't be an answer. However a much stronger complexity spec is given in the link, just scroll down to the "Complexity" heading. None of the standard algorithms take extra space unless otherwise noted. Apr 18, 2014 at 18:23
  • @Dukeling he didn't "just mention" it, and it's also not clear from the answer or the given link that the function won't delete your home directory.
    – jthill
    Apr 18, 2014 at 18:26
  • @jthill I guess we have different definitions of what "just mentioning" means. Either way, I don't see an explanation of how it works (or how it might be implemented) in the answer. Apr 18, 2014 at 18:33
  • The way you're using std::partition here basically makes it a radix sort.
    – nneonneo
    Apr 18, 2014 at 18:40
0

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).

0

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!

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.