Python: Sort unsorted numbers using Multi-key quicksort
Python Search and Sorting : Exercise-32 with Solution
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:
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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-32.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics