Quicksort algorithm is extendable to k-way partition

dutch-national-flag.py

#!/usr/bin/env python

def dutch_national_flag(arr):

    if arr is None or len(arr) <= 1:
        return


    red = 0
    blue = len(arr)-1
    i = 0

    while i <= blue:

        if arr[i] == 'R':
            arr[i], arr[red] = arr[red], arr[i]
            red += 1
            i += 1

        elif arr[i] == 'W':
            i += 1

        elif arr[i] == 'B':
            arr[i], arr[blue] = arr[blue], arr[i]
            blue -= 1

arr = ["W", "R", "R", "W", "B", "W", "R", "B", "R" ]
dutch_national_flag(arr)
print (arr)

four-way-partition.py

#!/usr/bin/env python

def fourwaypartition(arr):
    """
    This is an attempt to a four ways partition (extendable to more)
    """

    p1 = 0  # left to this boundary are elements equal to "!"
    p2 = 0  # left to this boundary are elements equal to "@"
    p3 = 0  # left to this boundary are elements equal to "#"
    p4 = 0  # left to this boundary are elements equal to "$"

    i = 0   # index walking through the array and inserting the element inside the
            #correspondant boundary

    while i < len(arr):


        if arr[i] == "!":
            #swap with the "!" boundary and make sure to shift all the other elements and their boundaries to the right.
            if (i > p1):
                arr[i], arr[p1] = arr[p1], arr[i]

            if (i > p2 and p2 > p1):
                arr[i], arr[p2] = arr[p2], arr[i]

            if (i > p3 and p3 > p2):
                arr[i], arr[p3] = arr[p3], arr[i]

            if (i > p4 and p4 > p3):
                arr[i], arr[p4] = arr[p4], arr[i]

            p1 += 1
            p2 += 1
            p3 += 1
            p4 += 1



        elif arr[i] == "@":
            # swap with the "@" boundary and make sure to shift all the other elements and their boundaries to the right.
            if (i > p2):
                arr[i], arr[p2] = arr[p2], arr[i]

            if (i > p3 and p3 > p2):
                arr[i], arr[p3] = arr[p3], arr[i]

            if (i > p4 and p4 > p3):
                arr[i], arr[p4] = arr[p4], arr[i]

            p2 += 1
            p3 += 1
            p4 += 1

        elif arr[i] == "#":
            # swap with the "#" boundary and make sure to shift all the other elements and their boundaries to the right.
            if (i > p3):
                arr[i], arr[p3] = arr[p3], arr[i]

            if (i > p4 and p4 > p3):
                arr[i], arr[p4] = arr[p4], arr[i]

            p3 += 1
            p4 += 1


        elif arr[i] == "$":
            # swap with the "$" boundary and make sure to shift all the other elements and their boundaries to the right.
            if (i > p4):
                arr[i], arr[p4] = arr[p4], arr[i]
            p4 += 1


        i += 1

        print("array %s" % arr)






arr = ["$", "$", "$", "@", "!", "$", "!", "@", "$", "$", "#", "$", "@", "!", "#", "!" ]
fourwaypartition(arr)

K-way-partition.md

Quick sort algorithm extendable to k-way sort

Quick sort can be distributed into two sub-tasks (quick sort left and right partitions) but can be also be distributed into three sub-tasks (or even more).

3 WAY PARTITION

The 3 ways distribution is useful for sorting an array with many duplicates.

3-ways partition code

Another typical problem is to sort by colors (e.g. Dutch National Flag problem).

Ducth national flag partition code

4 WAY PARTITION

Attempt to code a 4 way partition

k-ways-partition.png

three-way-partition

def three_way_partition(arr):
    if arr is None or len(arr) <= 1:
        return



    low = 0
    high = len(arr)-1
    i = 0

    pivot = arr[i]

    while i <= high:

        if arr[i] < pivot:
            arr[i], arr[low] = arr[low], arr[i]

            low += 1
            i += 1

        elif arr[i] == pivot:
            i += 1

        elif arr[i] > pivot:
            arr[i], arr[high] = arr[high], arr[i]
            high -= 1


arr = ["7", "10", "8", "7", "2", "9", "0", "7", "8", "10", "11", "9", "7", "3", "8", "3"]
three_way_partition(arr)
print (arr)