Dutch National Flag Algorithm. (Sort an array of 0s 1s 2s)

Dutch National Flag Algorithm: As per Wikipedia, The Dutch national flag problem is a computer science programming problem proposed by Edsger Dijkstra. The flag of Netherlands consists of three colors: red, white and blue. Given balls of those three colors arranged randomly during a line (it doesn't matter what percentage balls there are), the task is to rearrange them such all balls of the same color are together and their collective color groups are in the correct order. So, this algorithm is used segregate them according to their colors. This algorithm is also used to Sort an array containing 0s, 1s and 2s. Infact, this algorithm is an efficient approach to sort the array of 0s 1s 2s without using any sorting algorithm and Dutch National Flag has time complexity of O(n). We have to arrange them in such a order that all the 0s comes first, then 1s and at last 2s. Let us move on to Algorithm now to solve the problem.

Pseudo Code:

We will use three pointers here namely i, j and k. (Three pointers approach).
i = 0
j = 0
k = arr.length - 1
while(i <= j)

if(arr[j] == 0)
swap(arr[i], arr[j])
i++
j++

else if(arr[j] == 1)
j++

else if(arr[j] == 2)
swap(arr[k], arr[j])
k--

Code Approach: (JAVA)

public class Sort0s1s2s {

    public static void main(String[] args) {
        int[] arr = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 2, 0, 0, 0, 1};
        int n = arr.length;

        sort(arr); //calling sort method

        System.out.print("Sorted Arrays: ");
        printArray(arr, n); //printing sorted array
    }

    public static void printArray(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr) {
        int low = 0;
        int j = 0;
        int high = arr.length - 1;
        int temp;
        while (j <= high) {
            if (arr[j] == 0) {
                temp = arr[j];
                arr[j] = arr[low];
                arr[low] = temp;
                j++;
                low++;
            } else if (arr[j] == 1) {
                j++;
            } else if (arr[j] == 2) {
                temp = arr[j];
                arr[j] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }
}

Output:

Sorted Arrays: 0 0 0 0 0 0 0 1 1 1 1 1 2 2 2

Time Complexity: This algorithm has time complexity O(n), as whole array is traversed once.
Space Complexity: This algorithm has constant space complexity of O(1) as no extra space is required. This is an in-place algorithm.