Sort An Array Of 0s, 1s and 2s

Problem Statement:

You are given an array which contains the integers as 0s, 1s and 2s, your work is to sort the array such that the first interval is occupied by all 0s, the mid intervals are occupied by all 1s and the last intervals are occupied by all 2s.

Hint:

While designing an algorithm for the above problem, it’s common to think for a way by sorting the given array, but the time complexity of the merge sort will come out to be O(nlogn), but the best way to do the above problem is to design an algorithm within the time complexity of O(n) which can be easily done by the algorithm discussed below.

Quick Think:

For designing the above algorithm we need to ponder over the following points:-

• For creating the above algorithm we need to insert all the 0s at the starting of the array, 1s should be inserted at the mid-interval of the array and 2s should be inserted at the end of the arrays.
• For this we may think to swap the first element with the mid-interval is it is a 0, if it is 2 then we need to swap the element mid-interval 2s with that at the end interval of the array and decrement the right index.
• Now, since 0s and 2s are at their places now so we will not swap the 1s in the array and hence, they will remain in their places as we are swapping the other two elements with the help of this.

Algorithm:

Create a function named swap which will swap the elements in the array with the arguments as the first integer to be swapped and the second integer to be swapped together with this create another function for arranging the integers according to their required places with arguments as the array and size of the array.

Now after creating the above functions, we will follow the steps below to reach our final output:-

Step1: We will define the variables as the left, right and mid and initialize them as left = 0, right = size of the array - 1 and mid = 0.

Step2: Now traverse the array till mid <= right else go to step 6.

Step3: Since there are three integers to be sorted so we will use switch case and check for the elements in the array if the element is 0 then we will swap the array first array index element with the last index array element of the array and increment the index of both the variables by one else go to step 4.

Step4: Next we will see if the current element is 1 if yes, then increment the value of mid by one else go to step 5.

Step5: Next similarly, we will check if the element is 2 if yes, then we will swap the array mid index array element with the last index array element of the array and decrement the right index by one.

Step6: Terminate the loop.

Implementation Of The Above Algorithm:

#include<bits/stdc++.h>

using namespace std;
/* Function to swap the two array elements by using their address. */
void swap(int * a, int * b) {
  int temp;
  temp = * a;
  * a = * b;
  * b = temp;
}
/* Function to rearrange the array elements by using swap function. */
void rearrange(int arr[], int n) {
  int left = 0;
  int right = n - 1;
  int mid = 0;
  while (mid <= right) {
    switch (arr[mid]) {
    case 0:
      swap( & arr[mid++], & arr[left++]);
      break;
    case 1:
      mid++;
      break;
    case 2:
      swap( & arr[mid], & arr[right--]);
      break;
    }
  }
}
/* Function to print out the final array. */
void printarray(int arr[], int n) {
  int i;
  for (i = 0; i < n; i++)
    cout << arr[i] << " ";
}
/* Driver function to test the above algorithm. */
int main() {
  int arr[] = {
    0,
    1,
    2,
    0,
    1,
    2
  };
  int n = sizeof(arr) / sizeof(arr[0]);
  int i;

  rearrange(arr, n);

  cout << "Final Output" << endl;
  printarray(arr, n);
  return 0;
}

Time Complexity Of The Above Algorithm is O(n).

Output Of The Above Algorithm is: Final Output

0 0 1 1 2 2.

Explanation Of The Above Algorithm:

For an explanation of the above algorithm let us consider the array example as shown in the diagram above.

Now follow the steps below to reach the correct output:-

• After the declaration of the variables we will check for the array elements as the first array element is 0, so we will swap the element with the index left = 0 and mid = 0, hence there is no change in the array and the values of mid and left becomes 1 and 1 respectively as shown in the above diagram.

• Now we move on to the mid index element in the array which is 1 and so we increment the value of mid as 2, left = 1 and right = 5 as shown in the above diagram.

• Now, we move on to the next mid index element in the array and we have now, 2 hence, we swap the mid index element with the right index element in the array and decrement the right index by one as shown in the diagram above.

• Now, we move on to the next mid index element in the array and again we have now, 2 hence, we swap the mid index element with the right index element in the array and decrement the right index by one as shown in the diagram above.

• Now, we again move on to the next mid index element in the array and we have now, 1 hence, we so increment the value of mid as 3, left = 1 and right = 3 as shown in the above diagram.

• Now, we move on to the next mid index element in the array and again we have now, 0 hence, we swap the mid index element with the left index element in the array and increment the mid and the left index by one as shown in the diagram above.

• Now, since the mid index of the array is greater than the right index of the array and hence the loop terminates and we get the final array as our output as shown in the above diagram.