Sort a given binary array
The problem is to sort a given binary array containing only 0s and 1s. The goal is to rearrange the elements of the array in such a way that all 0s come first, followed by all 1s. The relative order of 0s and 1s within the sorted array should be the same as in the original array.
Example
Consider the following binary array:
[0, 1, 1, 0, 1, 0, 1, 1, 0, 1]
After sorting, the array becomes:
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
Idea to Solve the Problem
The problem can be efficiently solved using the Dutch National Flag algorithm, which was used in the previous explanation. However, in this specific case where there are only two distinct elements (0 and 1), we can perform a simpler and more efficient approach to sort the binary array in linear time.
Algorithm
- Initialize two pointers,
start
andend
, both pointing to the start of the array. - Iterate through the array using a loop from index 0 to
n - 1
(wheren
is the size of the array). - If the element at the current index is 0, swap it with the element at the
start
pointer and increment bothstart
and the current index. - If the element at the current index is 1, just increment the current index.
- Continue this process until the current index becomes greater than
end
.
Pseudocode
function sortBinaryArray(arr):
start = 0
end = size of arr - 1
while start <= end:
if arr[start] == 0:
swap arr[start] with arr[current index]
increment start and current index
else:
increment current index
end function
Time Complexity
- The above 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 constant-time swap or increment operations for each element.
- Therefore, the sorting algorithm is efficient for sorting binary arrays with a large number of elements.
Code Solution
-
1) Sort binary array using one traversal in java
2) Sort binary array using one traversal in c++
3) Sort binary array using one traversal in c
4) Sort binary array using one traversal in c#
5) Sort binary array using one traversal in php
6) Sort binary list using one traversal in python
7) Sort binary array using one traversal in ruby
8) Sort binary array using one traversal in scala
9) Sort binary array using one traversal in swift
10) Sort binary array using one traversal in kotlin
11) Sort binary array using one traversal in node js
12) Sort binary array using one traversal in vb.net
13) Sort binary array using one traversal in golang
14) Sort binary array using one traversal in typescript
Resultant Output Explanation
The given program implements the binary array sorting algorithm. It demonstrates the sorting process on the provided binary array.
In the provided output, the program displays the initial array elements before sorting and the array elements after sorting. The algorithm sorts the binary array in such a way that all 0s come first, followed by all 1s.
The output shows the sorted array, where all 0s are placed before all 1s, and the relative order of 0s and 1s within the array remains the same as in the original array.
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 will be correctly placed before the 1s.
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