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

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

Psuedo Code

for(i=0 -> N){for(j=i+1 -> N){if(A[i] > A[j]){Swap(A[i], A[j])}}}Print 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 which is even higher. Let’s see how we can optimize it to O)N).

Continue Reading.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Ateev Duggal

I am a front-end developer from India with over one year of experience in freelancing with skills like Git, HTML5, CSS3, Bootstrap 4&5, and React.