DEV Community

Luckshvadhan B
Luckshvadhan B

Posted on

Sort 0s, 1s, and 2s

Approach:
Step 1 Take the array
Step 2 Use three pointers low mid high
Step 3 Move elements based on value

if element is 0 swap with low move low and mid
if element is 1 just move mid
if element is 2 swap with high move high

Why this works???
The Array has only 0 1 2
so we group them in one pass
low for 0
mid for checking
high for 2
no need to sort full array

Code:
def sort012(arr):
low=0
mid=0
high=len(arr)-1
while mid<=high:
if arr[mid]== 0:
arr[low],arr[mid]=arr[mid],arr[low]
low+=1
mid+=1
elif arr[mid]==1:
mid+=1
else:
arr[mid],arr[high]=arr[high],arr[mid]
high-=1
return arr

Limitation:
Only works when array has 0 1 2
not for general sorting

Top comments (0)