Three way partitioning Python

PROGRAM TO PARTITION AN ARRAY AROUND A GIVEN RANGE

Given an array and a range [lowVal, highVal], partition the array around the range such that array is divided in three parts.
1) All elements smaller than lowVal come first.
2) All elements in range lowVal to highVVal come next.
3) All elements greater than highVVal appear in the end.
The individual elements of three sets can appear in any order.

  

# Partitions arr[0..n-1] around [lowVal..highVal]

def threeWayPartition(arr, n, lowVal, highVal):

  

    # Initialize ext available positions for

    # smaller (than range) and greater lements

    start = 0

    end = n - 1

    i = 0

  

    # Traverse elements from left

    while i <= end:

  

        # If current element is smaller than

        # range, put it on next available smaller

        # position.

        if arr[i] < lowVal:

            temp = arr[i]

            arr[i] = arr[start]

            arr[start] = temp

            i += 1

            start += 1

  

        # If current element is greater than

        # range, put it on next available greater

        # position.

        elif arr[i] > highVal:

            temp = arr[i]

            arr[i] = arr[end]

            arr[end] = temp

            end -= 1

  

        else:

            i += 1

  

# Driver code

if __name__ == "__main__":

    arr = [1, 14, 5, 20, 4, 2, 54, 

           20, 87, 98, 3, 1, 32]

    n = len(arr)

  

    threeWayPartition(arr, n, 10, 20)

  

    print("Modified array")

    for i in range(n):

        print(arr[i], end = " ")




OUTPUT

Modified array 
1 5 4 2 1 3 14 20 20 98 87 32 54 

CREDITS: https://www.geeksforgeeks.org/three-way-partitioning-of-an-array-around-a-given-range/