QuickSort using Random Pivoting using Python

Introduction

Sorting is a central operation in computer science, with applications going from information recovery to enhancing algorithm execution. Among different sorting algorithms, QuickSort stands out for its speed and productivity. Nonetheless, QuickSort's effectiveness intensely relies upon the decision of the pivot element. In this article, we dig into the idea of QuickSort and investigate a key upgrade: QuickSort utilizing Random Pivoting.

Understanding QuickSort

QuickSort is a famous and effective sorting algorithm that follows the "divide and conquer" paradigm. It works by choosing a pivot element from an array and parceling the array into two subarrays: elements not exactly the pivot and elements greater than the pivot. This interaction proceeds recursively on the subarrays until the whole array is arranged.

Pivot Determination in QuickSort

The decision of the pivot element assumes an urgent part in QuickSort's effectiveness. In the most dire outcome imaginable, when the pivot is reliably picked inadequately, QuickSort can corrupt into a quadratic-time algorithm, making it wasteful. To address this test, we present the idea of random pivoting.

Random Pivoting Strategy

Random Pivoting in QuickSort includes choosing the pivot element randomly from the array. Dissimilar to conventional pivot determination techniques, which could pick the first or last element as the pivot, random pivoting guarantees that the decision of the pivot is unusual. This randomness is the way to relieve most pessimistic scenario situations. The decision of the pivot element incredibly impacts QuickSort's performance. Conventional QuickSort executions frequently select the first or last element as the pivot. Be that as it may, this approach can prompt failure in specific situations, for example, when the info data is sorted. This is where Random Pivoting comes in.

Algorithm:

function quicksort(arr, low, high):
    if low < high:
        # Randomly select a pivot element
        pivot_index = randomly_select_pivot(arr, low, high)
        
        # Partition the array around the pivot and get the pivot's final position
        pivot_position = partition(arr, low, high, pivot_index)
        
        # Recursively sort the subarrays on both sides of the pivot
        quicksort(arr, low, pivot_position - 1)
        quicksort(arr, pivot_position + 1, high)

function randomly_select_pivot(arr, low, high):
    # Generate a random index between low and high
    pivot_index = random(low, high)
    return pivot_index

function partition(arr, low, high, pivot_index):
    # Swap the pivot element with the last element to simplify partitioning
    swap(arr[pivot_index], arr[high])
    pivot = arr[high]
    
    i = low  # Initialize the index for the smaller element
    
    for j = low to high - 1:
        if arr[j] <= pivot:
            # Swap arr[i] and arr[j] if the current element is smaller than or equal to the pivot
            swap(arr[i], arr[j])
            i = i + 1
    
    # Swap arr[i] and arr[high] to place the pivot in its final position
    swap(arr[i], arr[high])
    
    return i  # Return the index of the pivot element

function swap(a, b):
    # Helper function to swap two elements in an array
    temp = a
    a = b
    b = temp

Python Implementation:

Code

import random

def quicksort(arr):
    # Base case: If the array has 1 or fewer elements, it's already sorted.
    if len(arr) <= 1:
        return arr

    # Randomly select a pivot element
    pivot_index = random.randint(0, len(arr) - 1)
    pivot = arr[pivot_index]

    # Partition the array into three subarrays: lesser, equal, and greater than the pivot
    lesser = []
    equal = []
    greater = []

    for element in arr:
        if element < pivot:
            lesser.append(element)
        elif element == pivot:
            equal.append(element)
        else:
            greater.append(element)

    # Recursively sort the lesser and greater subarrays and combine them with the equal elements
    return quicksort(lesser) + equal + quicksort(greater)

if __name__ == "__main__":
    # Example usage:
    arr = [3, 6, 8, 10, 1, 2, 1]
    
    # Call the quicksort function to sort the array
    sorted_arr = quicksort(arr)
    
    # Display the original and sorted arrays
    print("Original array:", arr)
    print("Sorted array:", sorted_arr)

Output:

Original array: [3, 6, 8, 10, 1, 2, 1]
Sorted array: [1, 1, 2, 3, 6, 8, 10]

Conclusion

In conclusion, QuickSort with Random Pivoting is a strong sorting method with numerous partitioning choices, Lomuto and Hoare being two conspicuous decisions. The two methodologies influence the randomness of pivot choice to improve QuickSort's performance and versatility across different data situations. The given Python programs, combined with point-by-point remarks, offer a thorough asset for those keen on investigating and carrying out these algorithms in their projects.

Next TopicUsing Bioconductor from Python

← prev next →