CA 08 - Sort 0s, 1s, and 2s

Problem Statement: here

Problem Understanding:
From a given array consisting of 0s, 1s and 2s we have to arrange them in an ascending order and print the sorted array.

Solution:

arr = [0, 1, 2, 0, 1, 2]

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

print(arr)

• In this approach, we make use of three pointers low, mid and high.

• Initially, low and mid point to the first element of the array and high points to the last element of the array.

• Since we want 0s to the front of array, 1s in the middle of array and 2s to the back of array, we make sure the pointer mid is lesser than pointer high.

• We compare each value of the mid pointer, if arr[mid]= 0, then we interchange the index of mid and low, then increment mid and low.

• If arr[mid]= 2, we move 2 to the end of the array and decrement high.

• Else if arr[mid]=1, we do no operation and increment mid.

• The final array will have the sorted values.