algorithms EPICh6 kotlin

Problem 6.1 from EPI -> Variants 1,2,3

In the first variant of the problem 6.1 we have to sort an array such that all items with the same categories are grouped. If you think about it, this is the same as the pivot partition, check out the solution here.
Second variant is a bit more difficult, we need to group items that can fall into one of four categories. I used the same technique that can sort three categories but with a twist, we keep an index of group two right most item and group three left most item. When they cross it means we have solved the problem. We iterate through the array from the beginning and the end (in the three categories variant we need to just look at the items from the beginning), and keep incrementing end index (category three left most index) and beginning index (category two right most index). Check the solution here.
Third variant is quite simple, items can fall into one of two categories, we need to group them. This is easier than variant 1, we just keep an index for right most category 1 item and left most index for category 2 items and move new items into those categories. When those two indexes reach we are done. Check out the solution here.

Leave a Reply

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