Categories
algorithms EPICh6 kotlin

Problem 6.1 from EPI -> National Duch flag

So this one is interesting, the problem requires you to perform a crucial part of a quick sort algorithm the pivot ordering. Basically you need to pick a pivot, and move all elements that are less then the pivot to the left side of an array and bigger elements to the right side of the array. This can be done in various complexities as shown here in code. The trick with this problem is to realize you can make multiple passes for an array, it does not increase the complexity of the solution, so instead of sticking with one pass, break the algorithm into stages, and perform simpler algorithms in each stage. Those simpler algorithms combined will have a solution that works.

Leave a Reply

Your email address will not be published. Required fields are marked *