· · ·
Q: Sort a given binary array.
Input:
a = [1, 0, 1, 0, 1, 0, 0, 1]
Output:
[0, 0, 0, 0, 1, 1, 1, 1]
Algorithms:
- Logic:
- Iterate and fill available position with 0 if 0 found in list.
- Fill remaining positions with 1s.
- Complexity:
- Time: O(n)
- Space: O(1)
a = [1, 0, 1, 0, 1, 0, 0, 1]
k = 0
for i in a:
if i==0:
a[k] = 0
k += 1
for i in range(k, len(a)):
a[i] = 1
- Quicksort Logic:
- Complexity:
- Time: O(n)
- Space: O(1)
- Complexity:
a = [1, 0, 1, 0, 1, 0, 0, 1]
pivot = 1
start = 0
end = len(a) - 1
j = 0
while start < end:
if a[j] < pivot:
a[j], a[start] = a[start], a[j]
start += 1
j += 1
elif a[j] >= pivot:
a[j], a[end] = a[end], a[j]
end -= 1
REFERENCES:
500 Data Structures and Algorithms practice problems and their solutions
Sort binary array in linear time
· · ·