Python: Sort unsorted numbers using Random Pivot Quick Sort

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

31. Random Pivot Quick Sort

Write a Python program to sort unsorted numbers using Random Pivot Quick Sort. Pick a random index as the pivot.

Sample Solution:

Python Code:

#Ref.https://bit.ly/3pl5kyn
import random


def partition(A, left_index, right_index):
    pivot = A[left_index]
    i = left_index + 1
    for j in range(left_index + 1, right_index):
        if A[j] < pivot:
            A[j], A[i] = A[i], A[j]
            i += 1
    A[left_index], A[i - 1] = A[i - 1], A[left_index]
    return i - 1
def quick_sort_random(A, left, right):
    if left < right:
        pivot = random.randint(left, right - 1)
        A[pivot], A[left] = (
            A[left],
            A[pivot],
        )  # switches the pivot with the left most bound
        pivot_index = partition(A, left, right)
        quick_sort_random(
            A, left, pivot_index
        )  # recursive quicksort to the left of the pivot point
        quick_sort_random(
            A, pivot_index + 1, right
        )  # recursive quicksort to the right of the pivot point
nums = [4, 3, 5, 1, 2]
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 0, len(nums))
print(nums)
nums = [5, 9, 10, 3, -4, 5, 178, 92, 46, -18, 0, 7]
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 0, len(nums))
print(nums)
nums = [1.1, 1, 0, -1, -1.1, .1]
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 0, len(nums))
print(nums)
nums = [1.1, 1, 0, -1, -1.1, .1]
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 1, len(nums))
print(nums)
nums = ['z','a','y','b','x','c']
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 0, len(nums))
print(nums)
nums = ['z','a','y','b','x','c']
print("\nOriginal list:")
print(nums)
print("After applying Random Pivot Quick Sort the said list becomes:")
quick_sort_random(nums, 2, len(nums))
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 Random Pivot Quick Sort 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 Random Pivot Quick Sort 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 Random Pivot Quick Sort the said list becomes:
[1.1, -1.1, -1, 0, 0.1, 1]

Original list:
['z', 'a', 'y', 'b', 'x', 'c']
After applying Random Pivot Quick Sort the said list becomes:
['a', 'b', 'c', 'x', 'y', 'z']

Original list:
['z', 'a', 'y', 'b', 'x', 'c']
After applying Random Pivot Quick Sort the said list becomes:
['z', 'a', 'b', 'c', 'x', 'y']

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to implement quick sort that chooses a random pivot and then prints the pivot and resulting partitions.
• Write a Python script to sort a list using random pivot quick sort and count the average number of comparisons over multiple runs.
• Write a Python program to implement random pivot quick sort and verify that the sorted output matches that of the built-in sort.
• Write a Python function to perform random pivot quick sort on a list of integers and then analyze its performance on nearly sorted data.

Python Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Python program to sort unsorted numbers using Recursive Bubble Sort.
Next: Write a Python program to sort unsorted numbers using Multi-key quicksort.