How to Sort an Array of 0s, 1s and 2s in Java

Given an array A[] of 0s, 1s, and 2s of size N, the task is to write a function that can sort an array of 0s, 1s and 2s in ascending order such that 0s are in the beginning followed by all 1s and then 2s at the end, and without using any internal or inbuilt sorting function or library.

Examples

Well, there is no denying that that might be many approaches through which we can sort an array of 0s, 1s and 2s, but in this blog, we will only see 3 approaches that we think were the best and the easiest among all other approaches.

Let’s start…

Index

1. The Brute Force Approach
2. The Counting Approach
3. The Three Pointer Approach – Dutch National Flag Approach

The Brute Force Approach

In this approach, we are going to compare each number of the array with the one next to it while traversing the array from left to right. We can do this by using a nested loop system in which the outer loop will keep a track of the number and the inner loop will compare it with the rest of the elements of the array.

Algorithm

1. Use two loops for i and j=i+1 elements 
2. Compare them to see if the ith element is bigger than the jth element
3. If yes, swap their position so that the smaller element comes first as we have to arrange the elements in ascending order.
4. Print the array

Psuedo Code

package com.Tekolio.Arrays;
 
import java.util.Arrays;
 
public class Sort_0s_1s_2s {
    public static void main(String[] args) {
        int[] A = {0, 1, 2, 0, 1, 2};
        int n = A.length;
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                if(A[i] > A[j]) {
                    int temp = A[i];
                    A[i] = A[j];
                    A[j] = temp;
                }
            }
        }
        System.out.print(Arrays.toString(A));
    }
}

Output

A[] = [0, 0, 1, 1, 2, 2]

Time Complexity – O(N^2) Space Complexity – O(1)

We all know the time complexity of a sorting algorithm in N log N, but the above approach is taking the time complexity of N^2 which is even higher. Let’s see how we can optimize it to O)N).

The Counting Approach

The idea behind this approach is to first count all the occurrences of 0s, 1s, and 2s in the array and then based on that counting place the elements in the array using a loop, and those count values as thor start and end indexes.

Algorithm

1. Initialize three variables to store the number of occurrences of 0s, 1s, and 2s in the array, say c0, c1, and c2
2. Scan the array from left to right and trace the elements one by one.
3. Count the number of 0’s present in the array and store them in c0
4. Similarly, count the number of 1’s present in the array and store them in c1
5. And count the numbers of 2’s present in the array and store them in c2
6. We can do one more thing to get the count of 2s in the array. Subtract the count of 0s and 1s from the length of the array.
7. After counting all the 0’s, 1’s, and 2’s in the array, copy the values one by one back into array A.
8. For copying all the 0s in the array, we need a loop that will start from the 0th index till c0 
9. Similarly, for copying 1s, start the loop from c0 and run it till c0+c1. This is because we have to store 1s after 0s in the array.
10. Repeat the same process for copying 2s in the array, start the loop from c0+c1 till c0+c1+c2 or simply N.
11. Print the sorted array.

Pseudo Code

package com.Tekolio.Arrays;
 
import java.util.Arrays;
 
public class Sort_0s_1s_2s {
    public static void main(String[] args) {
        int[] A = {0, 1, 2, 0, 1, 2};
        int n = A.length;
        int c0 = 0;
        int c1 = 0;
        int c2 = 0;
        for(int i=0; i<n; i++) {
            if(A[i] == 0) {
                c0++;
            }
            if(A[i] == 1) {
                c1++;
            }
            if(A[i] == 2) {
                c2++;
            }
        }
        for(int i=0; i<c0; i++) {
            A[i] = 0;
        }
        for(int i=c0; i<c1+c0; i++) {
            A[i] = 1;
        }
        for(int i=c1+c0; i<n; i++) {
            A[i] = 2;
        }
        System.out.print(Arrays.toString(A));
    }
}

Output

A[] = [0, 0, 1, 1, 2, 2]

Time Complexity – O(N) Space Complexity – O(1)

Though the above approach is an optimized way to solve this problem there is still one problem, though the time complexity is linear but is not a perfect O(N) if analyzed correctly the time complexity of this approach is O(kN) and if we talk about this case, k=3 – time complexity of counting the 0s, 1s and 2s + the time complexity of placing them back into the array.

Now let’s a better approach than this which has a time complexity of O(N). 

The Three Pointer Approach

As the name suggests, this approach is dependent upon three-pointers which are usually named as low, mid, and high. These three pointers divide the array into four sections which are as follows – 

Section 1 

In this section, we will have all 0s and their range will be from 0 to low-1.

Section 2

Like the section 1 contains all 0s, this section will contain all 1s and its range will be from low to mid-1

Section 3

It will not contain any of the three values, or we can say posses unknown values which cannot predict and its range will be from mid to high – 1.

Section 4 

This section will be from high to the end of the array and will contain all 2s.

The basic idea of this approach is to place all the zeros on the left of the array and the 2s on the right while keeping the 1s at the center of the array, and all this is possible in only a single traversal of the array making the time complexity of this approach a perfect O(N) i.e. without any coefficient attached to it.

Algorithm 

1. As discussed, we first need to initialize the three-pointers which will divide the array into 4 parts. Let’s name them as low, mid, and high.
2. At the starting point, we could not differentiate which section contains all zeros and which contains all ones, and only twos. Hence initially, we will start the two pointers from index 0 in such a way that low = 0 and mid = 0. As for high, we start pointing it from the last index of the given array – N-1.
3. After that, we will run the loop, from mid to high, pointing from 0 to N-1.
4. In the loop, check if the value of the mid element is equal to 0, if that’s the case swap the mid element with the low one.
5. Increase the value of low and mid pointer by 1
6. If the mid pointer points to the value 1, we will only increase the mid pointer by 1.
7. And if the value of the mid element is equal to 2, swap the mid element with the high one.
8. Decrease the value of the high pointer by 1.
9. Once the loop is finished, print the array

Psuedo Code

package com.Tekolio.Arrays;
 
import java.util.Arrays;
 
public class Sort_0s_1s_2s {
    public static void main(String[] args) {
        int[] A = {0, 1, 2, 0, 1, 2};
        int low = 0;
        int mid = 0;
        int high = n-1;
        while(mid <= high) {
            if(A[mid] == 0) {
                int temp = A[low];
                A[low] = A[mid];
                A[mid] = temp;
                low++;
                mid++;
            }
            if(A[mid] == 1) {
                mid++;
            }
            if(A[mid] == 2) {
                 int temp = A [ mid ] ;  
                A [ mid ] = A [ high ] ;  
                A [ high ] = temp ;  
                high = high - 1 ;  
            }
        }
        System.out.print(Arrays.toString(A));
    }
}

Output

A[] = [0, 0, 1, 1, 2, 2]

Time Complexity – O(N) Space Complexity – O(1)

Conclusion

In this blog, we have discussed mainly 3 different ways in which we can sort an array of 0s, 1s, and 2s in such a way that 0s are in front followed by 1s and 2s at the end sorted array.

A single approach to that using the inbuilt sort functions and libraries to arrange them in ascending order, but that will take a time complexity of O(N log N) but we are told to do it in O(N) time complexity and O(1) space complexity. Thus we cannot use this method to sort the array.

So then we came up with some algorithms of ourselves like comparing the elements and arranging them in the ascending order, counting the number of zeros, ones, and twos and then placing them inside the array using that count, and lastly, the three-pointer approach which is also known Dutch National Flag Approach.

The time complexity of the brute force algorithm is O(N^2) as for the other two, they both have O(N) time complexity and we were asked to arrange the array in ascending order. And between the two approaches with O(N) time complexity, the three-pointer approach traverses the array only once, making it a perfect approach for O(N).

Frequently Asked Questions