DEV Community

Aniket Vaishnav
Aniket Vaishnav

Posted on

Sort arrays of zero's, one's and two's

This is a basic problem within understanding of array as a data structure and operations of sort as an algorithm upon the data structure.

Here we will start with the basics and crawl our way up with finding multiple constraints, hurdles or bottlenecks within our algorithm.

Approach 1

Simple sort

One obvious way is to use the known sorting techniques as section sort, or merge sort or quick sort.

The code goes here Simple Sorting Solution Or shown below

Simplest, but, no one want's it. As in such case we have making no use of the fact that we are having only 3 elements ie, 0, 1, and 2. Instade, we treated every number as a plain integer and sort it.

Approach 2

Hasing Solution

This one is slightly better, here we are taking into account how many times we have encountered, 0's 1's and 2's. Once that is known. By basic number system, we know all 0's occur before 1's and all 1's before 2's. In such a way, we fill up the array, as per the number of 0's then 1's and then 2's.

The code goes here Hashing Solution Or shown below

This too, have few problems

  1. What if the count which we are taking into consideration is out of bound from the integer limit. One can argue that in such cases we can take long value into consideration but still the limit hit's then? BigInteger? But this does not solve our problem. This in fact slows the system and makes it more prone to errors as the size of the array increases.

  2. What if the input is not a static data but a stream of data. In such cases, the input values will continue to come and not stop. In such case, our algorithm would halt upon the counting of 0's 1's and 2's step only, and not move forward. Hence, not making the in place streaming content sorted.

Approach 3

Poniters and Insertion

Upon seeing above hurdles, we come to know that the approach can be improved and adapted to new circumstances.

Here we can have the insertion point's within the array. These points will indicate where the incoming data could be inserted, for 0's 1's and 2's. For any such new upcoming streaming data, we need to look for the apt pointer within the 0, 1, and 2, then insert the upcoming data.

The code goes here Pointer and Insertion Solution Or shown below

In such a way we have, removed the hurdles from the approach for now.
This still seems to have a minor issue within scalability, like what if we have 0 1 2 and 3 within the digits.
In such cases we need to have multiple pointers for insertion and handling would be complex although if that would take place then the problem itself would be changed and would not be Sort Arrays of Zero's One's and Two's

Code </>

import java.util.Arrays;
/**
* Approach1
* Simple sort
* Simplest but, no one want's
*/
public class Approach1 {
public void sort012(int[] a) {
if (a == null || a.length == 0) {
throw new IllegalArgumentException("Array is null or empty");
}
Arrays.sort(a);
}
}
view raw Approach1.java hosted with ❤ by GitHub
/**
* Approach2
* hashing method
*/
public class Approach2 {
void sort012(int[] array) {
if (array == null || array.length == 0) {
throw new IllegalArgumentException("Array is null or empty");
}
/**
* The countTable will store count of 3 number's
* As, these 3 numbers are the content within the array
* ie,
* countTable[0] -> count of zero within the source array
* countTable[1] -> for 1 and so for countTable[2]
*/
int[] countTable = new int[3];
for (int number : array) {
countTable[number] += 1;
}
for (int i = 0; i < array.length; i++) {
// here we need to look for 3 content
// ie, 0 then 1 and then 2
// better to use for loop than writing 3 different
// if statements and having same logic within it.
for (int contnet = 0; contnet < 3; contnet++) {
if (countTable[contnet] >= 1) {
// we need to put zero here in array
array[i] = contnet;
// now the content has been used
// we need to decrement the count
// from the count table
countTable[contnet] -= 1;
// break the loop so we can get a next
// value for the i'th position within an array
break;
}
}
}
}
}
view raw Approach2.java hosted with ❤ by GitHub
import java.util.Arrays;
import java.util.Collections;
/**
* Approach3
*
* Pointers and Insertion Solution
*/
public class Approach3 {
void sort012(int[] a) {
if (a == null || a.length == 0) {
throw new IllegalArgumentException("Array is null or empty");
}
// take 3 pointers
// where we can insert the elemts
// we can say this as
// low, mid and high
// for 0 1 and 2
int low = 0;
int mid = 0;
// as 2 can be always appended to the end (being highest)
int high = a.length - 1;
/***
* Life would be super easy if we had
* only 0 and 2,
* just insert from left in case of 0
* and just insert from right in case of 2
*
* but with 1 we take mid into consideration
* and parse the mid from 0 (which is assigned initally)
* to the apt location till the point it is valid
* and does not bump into high
*/
while (mid <= high) {
switch (a[mid]) {
case 2:
// here we need to insert at the high position
// and decrement the pointer for any upcoming 2
// swap the high and mid as it's quite possible
// that while inserting to high original value within
// that place would be lost,
// which is what we do not want to occur
swap(a, high, mid);
high -= 1;
break;
case 1:
// it's alright to find 1 at place of mid
// it is what is meant to
// only thing to do is check for the next position
mid++;
break;
case 0:
// here if we see any 0 we insert into low place
// and increment the pointer for any upcoming 0
// at this point we found 0 at mid.
// give this from mid to low
// as low have all zero
// best way to exchange an element is by swap
swap(a, low, mid);
low++;
mid++;
break;
default:
throw new IllegalArgumentException("Corrupted array!");
}
}
}
void swap(int[] a, int l, int r) {
int t = a[l];
a[l] = a[r];
a[r] = t;
}
}
view raw Approach3.java hosted with ❤ by GitHub

Billboard image

Monitoring as code

With Checkly, you can use Playwright tests and Javascript to monitor end-to-end scenarios in your NextJS, Astro, Remix, or other application.

Get started now!

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay