Sort an Array of 0s 1s And 2s

Problem Statement

We are given an array consisting of only 0s, 1s, and 2s. Our task is to write a program to sort the given array without using inbuilt functions.

Example

Example Explanation

Since we already know that an array is a linear data structure that contains data elements of the same data type at contiguous memory locations. For example, an array containing 12 elements as follows -[0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0].

Sorting an array means arranging of data elements in ascending or descending order, so our task here is to sort it in ascending order. Therefore, in our resultant sorted array, all 0s must come before all the 1s and all 1s must come before all 2s.

Thus, the sorted array will be [0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

Constraints

1 <= n <= 10^6 , here n is the number of elements in the array A 0 <= A[i] <= 2 , here A[i] is the value of every ith element in the array A

Approach 1: By Brute force method using double traversal

• Intuition: The first idea that comes into our mind since there are only 3 distinct values, is to just count the number of 0s, 1s and 2s. So we will be using 3 different variables to store these values which will be followed by overwriting the array with the help of these count variables.

  This problem is similar to three-way partitioning for the Dutch national flag problem.

• Algorithm:

  1. Initialize 3 variables count0, count1, count2 to store the count of 0s, 1s, and 2s respectively.
  2. Traverse through the array and increase count0 if the element is 0, increase count1 if the element is 1 and increase count2 if the element is 2.
  3. Now traverse the array again and overwrite the first count0 positions in the array with 0, the next count1 positions with 1, and the remaining count2 with 2.

• Implementation

  C++ Program to sort an array of 0s 1s and 2s using Brute Force method:

  Java Program to sort an array of 0s 1s and 2s using Brute Force method:

  Python Program to sort an array of 0s 1s and 2s using the Brute Force method:

  Output

• Complexity Analysis

  In the above approach, we require traversing the array twice; once to count the number of 0s, 1s, and 2s. While the second traversal is required to store the values at their sorted places in the array, that means we need to copy all the n elements. T(n) = O(n) + O(n)

  Hence, Time complexity will be - T(n) = O(n)

  Also, we observe that no extra space is required to store the elements.

  Hence, Space complexity will be - S(n) = O(1)

Approach 2: By using a single traversal method named the three-way partitioning

• Intuition: In this approach we will be using 3-pointers low, mid, high. We will use these pointers to place all 0s to the left end, all 2s to the right end, and all 1s in the middle of the array, hence making the array sorted.

• Algorithm:

  1. Initialize 3 pointers low = 0, mid = 0 and high = N-1.

  2. Start traversing the array from start to end, repeat this process until mid <= high.

     • If the A[mid]==0, then swap(A[low], A[mid]) and update the pointers low = low + 1 and mid = mid + 1.
     • If the A[mid]==1, just update the pointer mid = mid + 1.
     • If the A[mid]==2, then swap(A[mid], A[high]) and update the pointer high = high - 1

  3. Print the sorted array

• Implementation:

  C++ Program to sort an array of 0s 1s and 2s using three-way partitioning:

  Java Program to sort an array of 0s 1s and 2s using three-way partitioning:

  Python Program to sort an array of 0s 1s and 2s using three-way partitioning:

  Output

• Complexity Analysis

  In this approach, we require traversing the array only once for comparing the value present at mid index with 0, 1, and 2 and swapping them if necessary. After the traversal is done, the result will be a sorted array. T (n) = C + O (n)
  Here C is the constant time taken for swapping the values in the variables.

  Hence Time complexity will be - T(n) = O(n)

  Also, we observe that no extra space is required to store the elements.

  Hence Space complexity will be - S(n) = O(1)