If you’re a JavaScript developer, chances are you’ve encountered the Data Structure question to sort an array of 0s, 1s, and 2s.

In this article, we’ll explore the most efficient way to sort an array of 0s, 1s, and 2s in JavaScript. We’ll start with over with an overview of the question and then dive into the implementation details along with code .

Problem Statement

We’re given an array of integers that can only contain the values 0, 1, or 2. Our goal is to sort the array in ascending order.

For example, given the array [2, 0, 2, 1, 1, 0], the sorted array should be [0, 0, 1, 1, 2, 2].

Solution Explanation using Pseudo Algorithm

1. Simple Beginners Way

The simplest approach to sorting an array of 0s, 1s, and 2s is to use a sorting algorithm like bubble sort or insertion sort. However, these algorithms have a time complexity of O(n^2), which makes them inefficient for large arrays.

Another approach is to use the built-in sort() method provided by JavaScript arrays. However, this method also has a time complexity of O(n^2) in the worst-case scenario.

2 . Advanced Method

The most efficient way to sort an array of 0s, 1s, and 2s is to use the Dutch national flag algorithm, also known as the 3-way partitioning algorithm. This algorithm was designed by Edsger W. Dijkstra, a Dutch computer scientist.

The Dutch national flag algorithm is a linear-time sorting algorithm that partitions an array into three parts: elements less than a given value, elements equal to the given value, and elements greater than the given value.

To sort an array of 0s, 1s, and 2s, we can use the Dutch national flag algorithm with the given value being 1. Here’s how it works:

• Initialize three pointers low, mid, and high.
• low and mid point to the first element of the array, and high points to the last element of the array.
• While mid is less than or equal to high:
• If the value at mid is 0, swap the value at mid with the value at low and increment both low and mid.
• If the value at mid is 1, increment mid.
• If the value at mid is 2, swap the value at mid with the value at high and decrement high.
• The array is now sorted.

Code for Sorting array of 0s, 1s, and 2s

function sortArray(array) {
  let low = 0;
  let mid = 0;
  let high = array.length - 1;
  while (mid <= high) {
    if (array[mid] === 0) {
      [array[low], array[mid]] = [array[mid], array[low]];
      low++;
      mid++;
    } else if (array[mid] === 1) {
      mid++;
    } else if (array[mid] === 2) {
      [array[mid], array[high]] = [array[high], array[mid]];
      high--;
    }
  }
  return array;
}

const array = [2, 0, 2, 1, 1, 0];
const sortedArray = sortArray(array);
console.log(sortedArray); // [0, 0, 1, 1, 2, 2]

Code Explanation

In this implementation, we initialize three pointers: low, mid, and high. low and mid point to the first element of the array, and high points to the last element of the array.

We use a while loop to iterate over the array while mid is less than or equal to high. Inside the loop, we use if-else statements to handle each of the three cases:

1. If the value at mid is 0, we swap the value at mid with the value at low and increment both low and mid.
2. If the value at mid is 1, we simply increment mid.
3. If the value at mid is 2, we swap the value at mid with the value at high and decrement high.

After the loop, the array is now sorted, and we simply return it.