This post is a part of the Interview Question Series posts.
Three way partition?! Is there a two way partition or a four way partition ?!
Well X way partition problems are simply dividing the array/collection into X compartments each with it's own distinct feature/property.
One way compartment sort is too simple (just return the array without doing anything) 🙂
Two compartments are not difficult as well – you just need to pointers one to the left side one to the right side and you advance the pointers from both sides towards middle when you can't move you swap between them. And the main loop is running while the left side hasn't crossed the right side. If you want the code just drop me a line…
The complexity is greatly increases when the number of compartments is more then two (and you bound to a memory complexity of O(1) – otherwise one could create a list per compartment, go through the source array and map the items to the corresponding list and at the end just merge the lists by the needed order).
So, what are our options – we can sort using some sort efficient sort – O(NlogN). Quite good but can we do better ? The answer is yes (otherwise I wouldn't bother…)
You can generalize the algorithm using generics by providing a mapping function that maps the item to specific compartment (1, 2 or 3) as following:
And in order to solve the problem above all you need is to create the correct mapping as following: