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)
- Initialize three pointers,
low
,mid
, andhigh
, pointing to the start, start, and end of the array, respectively. - The
low
pointer is used to store the current position for 0s. - The
high
pointer is used to store the current position for 2s. - The
mid
pointer is used to traverse the array. - While
mid
is less than or equal tohigh
, do the following: a. If the element atmid
is 0, swap it with the element atlow
, incrementlow
andmid
. b. If the element atmid
is 1, just incrementmid
. c. If the element atmid
is 2, swap it with the element athigh
, decrementhigh
. - Continue this process until
mid
becomes greater thanhigh
.
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.
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.
New Comment