Sort an array of 0’s, 1’s and 2’s

Approach: Count the number of 0s, 1s and 2s in the given array. Then store all the 0s in the beginning followed by all the 1s then all the 2s. Algorithm: 1)Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s 2)Traverse through the array and increase the count of c0 is the element is 0,increase the count of c1 if the element is 1 and increase the count of c2 if the element is 2 3)Now again traverse the array and replace first c0 elements with 0, next c1 elements with 1 and next c2 elements with 2. //GfG PseudoCode

# Utility function to swap elements `A[i]` and `A[j]` in the list
def swap(A, i, j):
 
    temp = A[i]
    A[i] = A[j]
    A[j] = temp
 
 
# Linear time partition routine to sort a list containing 0, 1, and 2.
# It is similar to 3–way partitioning for the Dutch national flag problem.
def threeWayPartition(A, end):
 
    start = mid = 0
    pivot = 1
 
    while mid <= end:
        if A[mid] < pivot:    # current element is 0
            swap(A, start, mid)
            start = start + 1
            mid = mid + 1
        elif A[mid] > pivot: # current element is 2
            swap(A, mid, end)
            end = end - 1
        else:                # current element is 1
            mid = mid + 1

Posted by: Guest on February-02-2021

Code answers related to "Sort an array of 0’s, 1’s and 2’s"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Answers for "Sort an array of 0’s, 1’s and 2’s"

Code answers related to "Sort an array of 0’s, 1’s and 2’s"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us