{"post":"

PROBLEM: An array consists of only 0,1 and 2 as its elements. You have to sort it.

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]

# Algorithm

Pseudo Code:

We will calculate the number of 0s, 1s and 2s in the entire array.
Thus, get the count of each individual tokens.
Now, We’ll start from the beginning and place the number of 0s in the starting count_of_zero indices.
We then place the number of 1s in the next count_of_ones indices.
At last, we place the number of 2s in the count_of_twos indices.

Code:

#include <bits/stdc++.h>\r\nusing namespace std;\nvoid sortArray(int arr[], int size)\r\n{\r\nint iterator, count_of_zeroes = 0, count_of_ones = 0, count_of_twos = 0;
\nfor (iterator = 0; iterator&lt; size; iterator++)\r\n{\r\n\tswitch (arr[iterator])\r\n\t{\r\n\t\tcase 0:\r\n\t\t\tcount_of_zeroes++;\r\n\t\t\tbreak;\r\n\t\tcase 1:\r\n\t\t\tcount_of_ones++;\r\n\t\t\tbreak;\r\n\t\tcase 2:\r\n\t\t\tcount_of_twos++;\r\n\t\t\tbreak;\r\n\t}\r\n}\r\n\r\niterator = 0;\r\nwhile (count_of_zeroes &gt; 0)\r\n{\r\n\tarr[iterator++] = 0;\r\n\tcount_of_zeroes--;\r\n}\r\n\r\nwhile (count_of_ones &gt; 0)\r\n{\r\n\tarr[iterator++] = 1;\r\n\tcount_of_ones--;\r\n}\r\n\r\nwhile (count_of_twos &gt; 0)\r\n{\r\n\tarr[iterator++] = 2;\r\n\tcount_of_twos--;\r\n}\r\n\r\nfor (int iterator = 0; iterator&lt; size; iterator++)\r\n\tcout &lt;&lt; arr[iterator] &lt;&lt; \" \";\n
\n}
\nint main()\r\n{\r\nint arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };\r\ncout << \"Sorted array is { \";\r\nsortArray(arr, 12);\r\ncout << \"} \" << endl;\r\nreturn 0;\r\n}

Output:

Sorted array is { 0,0,0,0,0,1,1,1,1,1,2,2 }

Time Complexity: O(N)

Space Complexity: O(1)

This is how we sort an array of 0s 1s and 2s. This is identical to the problem of Dutch National Flag, just using numbers instead of the colors.

\n","title":"Sort an array of 0s, 1s and 2s Problem","authorDetails":{"name":"Anshuman Raina","slug":"anshuman-raina"},"description":"An array consists of only 0,1 and 2 as its elements. You have to sort it in C++. We start from the beginning and place the number of 0s in the starting count_of_zero indices.","slug":"sort-an-array-of-0s-1s-and-2s/","articleId":"636a83447bb1ce5072622b7d","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}