The Sort Color problem expects to sort the array with values {0, 1, 2}. This can be done in a typical sorting algorithm in O(nlogn) time. A better approach is to use three-way partitioning of the array. Generic three-way partitioning Below the threeWayPartitionSort() method splits the given an array, [3,2,0,2,1,1,0,-1], into three parts, where values […]
Tag: Java
Categories
LeetCode: Find Peak Element Solution
The Find Peak Element problem can be solved using a linear search in O(n) time and O(1) space. but it can be even better to solve it by binary search in O(log n) time complexity. But there can be two cases for binary search solution, the recursive solution creates stacks for each call and thus […]
This class implements a QuickSort algorithm using Hoare Paritioning scheme. This partitionining scheme is slightly harder to implement but is more efficient than the Lamuto partitioning scheme as it does three times fewer swaps on average [Wikipedia]. Avg Time-Complexity: O(nlogn) Worst Time-Complexity: O(n^2) Space complexity: O(1) Understanding Hoare Partition Intuitively After spending quite some on […]
Categories