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

Code Solution

Solution by using counting

1) Sort an array of 0s 1s and 2s in java 2) Sort an array of 0s 1s and 2s in c++ 3) Sort an array of 0s 1s and 2s in c 4) Sort an array of 0s 1s and 2s in c# 5) Sort an array of 0s 1s and 2s in php 6) Sort an array of 0s 1s and 2s in node js 7) Sort an list of 0s 1s and 2s in python 8) Sort an array of 0s 1s and 2s in ruby 9) Sort an array of 0s 1s and 2s in scala 10) Sort an array of 0s 1s and 2s in swift 11) Sort an array of 0s 1s and 2s in kotlin 12) Sort an array of 0s 1s and 2s in golang 13) Sort an array of 0s 1s and 2s in vb.net 14) Sort an array of 0s 1s and 2s in typescript

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.