Suppose you are given an array of n elements containing two distinct keys - 0 and 1. How will you design a linear time algorithm to sort the array.
(Method 1) :: Using constant storage
Calculating countZero and printing the array both takes \( O(n) \) time. Therefore, time complexity of the algorithm = \( O(n) + O(n) = O(n) \). public static void sortZeroAndOne(int[] array, int n){ (Method 2) :: Without using storage
Since the two pointers move towards each other from the two end points and the algorithm ends when they cross, running time of the algorithm = \( O(n) \). public static void sortZeroAndOne(int[] array){ |