Python: Sort unsorted numbers using Multi-key quicksort

Last update on April 02 2025 05:25:56 (UTC/GMT +8 hours)

32. Multi-key Quick Sort

Write a Python program to sort unsorted numbers using Multi-key quicksort.

From Wikipedia-
Multi-key quicksort:
This algorithm is a combination of radix sort and quicksort. Pick an element from the array (the pivot) and consider the first character (key) of the string (multikey). Partition the remaining elements into three sets: those whose corresponding character is less than, equal to, and greater than the pivot's character. Recursively sort the "less than" and "greater than" partitions on the same character.

Sample Solution:

Python Code:

#Ref.https://bit.ly/36fvcEw
def quick_sort_3partition(sorting: list, left: int, right: int) -> None:
    if right <= left:
        return
    a = i = left
    b = right
    pivot = sorting[left]
    while i <= b:
        if sorting[i] < pivot:
            sorting[a], sorting[i] = sorting[i], sorting[a]
            a += 1
            i += 1
        elif sorting[i] > pivot:
            sorting[b], sorting[i] = sorting[i], sorting[b]
            b -= 1
        else:
            i += 1
    quick_sort_3partition(sorting, left, a - 1)
    quick_sort_3partition(sorting, b + 1, right)
def three_way_radix_quicksort(sorting: list) -> list:
    if len(sorting) <= 1:
        return sorting
    return (
        three_way_radix_quicksort([i for i in sorting if i < sorting[0]])
        + [i for i in sorting if i == sorting[0]]
        + three_way_radix_quicksort([i for i in sorting if i > sorting[0]])
    )
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_3partition(nums, 0, len(nums)-1)
print(nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
print("After applying Multi-key quicksort the said list becomes:")
quick_sort_3partition(nums, 0,  len(nums)-1)
print(nums)
nums = [1.1, 1, 0, -1, -1.1, .1]
print("\nOriginal list:")
print(nums)
print("After applying Multi-key quicksort the said list becomes:")
quick_sort_3partition(nums, 0, len(nums)-1)
print(nums)
nums = [1.1, 1, 0, -1, -1.1, .1]
print("\nOriginal list:")
print(nums)
print("After applying Multi-key quicksort the said list becomes:")
quick_sort_3partition(nums, 1,  len(nums)-1)
print(nums)
nums = ['z','a','y','b','x','c']
print("\nOriginal list:")
print(nums)
print("After applying Multi-key quicksort the said list becomes:")
quick_sort_3partition(nums, 0, len(nums)-1)
print(nums)
nums = ['z','a','y','b','x','c']
print("\nOriginal list:")
print(nums)
print("After applying Multi-key quicksort the said list becomes:")
quick_sort_3partition(nums, 2,  len(nums)-1)
print(nums) 

Sample Output:

Original list:
[4, 3, 5, 1, 2]
After applying Random Pivot Quick Sort the said list becomes:
[1, 2, 3, 4, 5]

Original list:
[5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
After applying Multi-key quicksort the said list becomes:
[-18, -4, 0, 3, 5, 5, 7, 9, 10, 46, 92, 178]

Original list:
[1.1, 1, 0, -1, -1.1, 0.1]
After applying Multi-key quicksort the said list becomes:
[-1.1, -1, 0, 0.1, 1, 1.1]

Original list:
[1.1, 1, 0, -1, -1.1, 0.1]
After applying Multi-key quicksort the said list becomes:
[1.1, -1.1, -1, 0, 0.1, 1]

Original list:
['z', 'a', 'y', 'b', 'x', 'c']
After applying Multi-key quicksort the said list becomes:
['a', 'b', 'c', 'x', 'y', 'z']

Original list:
['z', 'a', 'y', 'b', 'x', 'c']
After applying Multi-key quicksort the said list becomes:
['z', 'a', 'b', 'c', 'x', 'y']

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to implement multi-key quick sort on a list of strings and sort them based on their first two characters.
• Write a Python script to perform multi-key quick sort on a list of tuples using two keys, then output the sorted list.
• Write a Python program to sort a list of alphanumeric strings using multi-key quick sort and compare the result with natural sort.
• Write a Python function to implement multi-key quick sort on a list of dictionaries based on multiple specified keys.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort unsorted numbers using Random Pivot Quick Sort. Picks the random index as the pivot.
Next: Write a Python program to sort unsorted numbers using Pigeonhole sorting.