# Sort an array of 0s 1s and 2s

The problem is to sort an array of 0s, 1s, and 2s in non-decreasing order. The array contains only three distinct elements: 0, 1, and 2. The goal is to rearrange the elements of the array in such a way that all 0s come first, followed by all 1s, and then all 2s.

## Example

Consider the following array:

``[0, 1, 0, 2, 2, 1, 2, 0, 0, 2, 0, 1, 1, 0, 2]``

After sorting, the array becomes:

``[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]``

## Idea to Solve the Problem

The problem can be efficiently solved using the Dutch National Flag algorithm, also known as the Three-Way Partitioning algorithm. The algorithm is a linear-time sorting algorithm that allows rearranging elements in the array in a specific order.

## Algorithm (Dutch National Flag Algorithm)

1. Initialize three pointers, `low`, `mid`, and `high`, pointing to the start, start, and end of the array, respectively.
2. The `low` pointer is used to store the current position for 0s.
3. The `high` pointer is used to store the current position for 2s.
4. The `mid` pointer is used to traverse the array.
5. While `mid` is less than or equal to `high`, do the following: a. If the element at `mid` is 0, swap it with the element at `low`, increment `low` and `mid`. b. If the element at `mid` is 1, just increment `mid`. c. If the element at `mid` is 2, swap it with the element at `high`, decrement `high`.
6. Continue this process until `mid` becomes greater than `high`.

## Pseudocode

``````function sortArray(arr):
low = 0
mid = 0
high = size of arr - 1

while mid <= high:
if arr[mid] == 0:
swap arr[low] with arr[mid]
increment low and mid
else if arr[mid] == 1:
increment mid
else:
swap arr[mid] with arr[high]
decrement high

end function``````

## Time Complexity

• The Dutch National Flag algorithm has a time complexity of O(N), where N is the number of elements in the array. This is because we traverse the array once and perform a constant-time swap or increment/decrement operation for each element.
• Therefore, the sorting algorithm is efficient for sorting arrays with a large number of elements.

## Resultant Output Explanation

The given program implements the Dutch National Flag algorithm to sort arrays containing 0s, 1s, and 2s. It demonstrates the sorting process on two different input arrays.

In the provided output, the program displays the initial array elements before sorting and the array elements after sorting. The algorithm sorts the arrays in non-decreasing order, with all 0s first, followed by all 1s, and then all 2s.

The output shows the arrays in the desired sorted order after applying the Dutch National Flag algorithm.

Note: The specific order of the sorted elements may vary each time the program is executed, as the sorting is deterministic but not stable. However, the elements of 0s, 1s, and 2s will be correctly grouped together in ascending order.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.