Lab 05: Randomized Algorithms

Randomized algorithms introduce an element of unpredictability that can lead to improved average-case performance and simpler implementations. In this lab, we demonstrate randomness in algorithms using the classic Quicksort algorithm, which becomes highly efficient when its pivot is selected randomly.

Introduction

Quicksort is a divide-and-conquer algorithm that sorts a list by selecting a pivot, partitioning the array around it, and recursively sorting the sub-arrays. While its worst-case time complexity is $O(n^2)$, choosing the pivot randomly can drastically improve its average performance to $O(n \log n)$.

This practical focuses on:

• Understanding how random pivot selection affects performance.
• Comparing randomized vs. deterministic Quicksort.
• Visualizing the sorting process for intuition.

Quicksort: Deterministic vs. Randomized

1. Deterministic Quicksort (Pivot: Last Element)

def quicksort_deterministic(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[-1]
    left = [x for x in arr[:-1] if x <= pivot]
    right = [x for x in arr[:-1] if x > pivot]
    return quicksort_deterministic(left) + [pivot] + quicksort_deterministic(right)

2. Randomized Quicksort (Pivot: Random Element)

import random
 
def quicksort_randomized(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    arr_copy = [x for x in arr if x != pivot]
    left = [x for x in arr_copy if x <= pivot]
    right = [x for x in arr_copy if x > pivot]
    return quicksort_randomized(left) + [pivot] + quicksort_randomized(right)

Example Usage

arr = [5, 3, 8, 4, 2, 7, 1, 6]
 
sorted_deterministic = quicksort_deterministic(arr)
sorted_randomized = quicksort_randomized(arr)
 
print("Original:", arr)
print("Sorted (Deterministic):", sorted_deterministic)
print("Sorted (Randomized):", sorted_randomized)

Visualization

import matplotlib.pyplot as plt
 
def visualize_quicksort(arr, quicksort_func, title):
    snapshots = []
 
    def quicksort_track(arr):
        if len(arr) <= 1:
            return arr
        pivot = random.choice(arr)
        arr_copy = [x for x in arr if x != pivot]
        left = [x for x in arr_copy if x <= pivot]
        right = [x for x in arr_copy if x > pivot]
        snapshot = left + [pivot] + right
        snapshots.append(snapshot)
        return quicksort_track(left) + [pivot] + quicksort_track(right)
 
    quicksort_track(arr.copy())
 
    for i, snapshot in enumerate(snapshots):
        plt.bar(range(len(snapshot)), snapshot, color='skyblue')
        plt.title(f"{title} - Step {i+1}")
        plt.xlabel("Index")
        plt.ylabel("Value")
        plt.show()
 
# Run visualization
arr = [8, 4, 2, 6, 7, 5, 1, 3]
visualize_quicksort(arr, quicksort_randomized, "Randomized Quicksort")

Time and Space Complexity

*Worst case is rare due to randomization.

Applications

1. Sorting large datasets: Randomized Quicksort is widely used in standard libraries.
2. Quick decision-making: In randomized optimization or game simulations.
3. Benchmarking randomness effects: Helps study average-case behavior of algorithms.

Conclusion

Randomized Quicksort is a powerful demonstration of how randomness can improve algorithmic performance. With only a minor tweak (random pivot), we significantly reduce the chance of worst-case scenarios, leading to faster average runtimes in practice.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
   Introduction to Algorithms, 3rd/4th Edition, MIT Press.

2. YouTube: Randomized Quicksort Visualized