w3resource

Python: Sort unsorted numbers using Random Pivot Quick Sort


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:

Flowchart: Python Data Structures and Algorithms: Sort unsorted numbers using Random Pivot Quick Sort.

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.

Go to:


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.

Python Code Editor:

Contribute your code and comments through Disqus.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.