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

Input: {0, 1, 2, 0, 1, 2}
Output: {0, 0, 1, 1, 2, 2}
Input: {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1}
Output: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

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

Pseudo Code

for(i=0 -> N)
{
   for(j=i+1 -> N)
   {
      if(A[i] > A[j])
      {
         Swap(A[i], A[j])
      }
   }
}
Print A

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²) 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² which is even higher. Let’s see how we can optimize it to O)N).

Continue Reading.