Randomized Quick Sort

Quicksort is one of the most classic sorting algorithms in computer science, known for its average-case time complexity of O(n log n). However, when the input data is already sorted or nearly sorted, traditional quicksort degrades to O(n²) time complexity. Randomized quicksort cleverly solves this problem by introducing randomness.

Before diving into randomized quicksort, let us first review the core idea of traditional quicksort.

How Quick Sort works

Quick Sort usesDivide and Conquer Strategy, the basic steps are as follows:

  1. Select pivot valueChoose an element from the array as the pivot value.
  2. Partition OperationReorder the array so that all elements smaller than the pivot are placed before it, and all elements greater than the pivot are placed after it.
  3. recursively sortRecursively apply the same process to the subarrays on both sides of the pivot.

Problems with traditional Quick Sort

The performance of traditional quicksort is highly dependent on the choice of pivot. The algorithm is most efficient when the pivot can roughly split the array into two equal halves each time. However, performance degrades significantly in the following cases:

  • Sorted ArrayIf the array is already sorted, choosing the last element as the pivot each time leads to extremely unbalanced partitions.
  • Reverse-Order ArraySimilar to a sorted array, but in the opposite direction.
  • Duplicate ElementsA large number of duplicate elements can also cause unbalanced partitions.

In these worst-case scenarios, quicksort's time complexity degrades to O(n²), comparable to simple algorithms such as bubble sort.

Randomized quicksort avoids worst-case scenarios by introducing randomness, ensuring that the algorithm maintains good average performance across various inputs.

The core improvement of randomized quicksort is very simple:Randomly select the pivotRather than always choosing the first, last, or middle element, a random element is selected as the pivot. This randomness makes the probability of the worst case extremely low, thereby ensuring an expected time complexity of O(n log n).

Basic idea of randomized Quick Sort:Through a single pass of sorting, the data to be sorted is divided into two independent parts, where all data in one part is smaller than all data in the other part. Then, quicksort is applied recursively to each of these two parts. The entire sorting process can proceed recursively, thereby turning the whole data into an ordered sequence.

Algorithm Advantages

Features Traditional Quick Sort Randomized Quick Sort
Worst-case time complexity O(n²) O(n²) (but with extremely low probability)
Average-case time complexity O(n log n) O(n log n)
Conditions for the worst case Specific inputs (such as already-sorted arrays) The random selection happens to always pick the extreme value
Space complexity O(log n) (recursive stack) O(log n) (recursive stack)
Stability unstable unstable

Although the worst-case time complexity of randomized quicksort is still O(n²) in theory, in practice the probability of this worst case occurring is extremely low. For an array of n elements, the probability that randomly selecting pivots leads to the worst case is approximately 1/n!, which is almost impossible in practice.

Process Diagram

In an array, select a pivot, for example the 4 at the first position, then move the 4 to its correct position so that the data in the preceding subarray is less than 4 and the data in the following subarray is greater than 4, and then recursively continue until the entire sort is completed.

How to move the selected pivot data to its correct position is the core of quicksort, and we call this process Partition.

The process is as follows, whereiis the position of the element currently being traversed and compared:

This partition process is expressed in code as:

Example

    ...
private static int partition(Comparable[] arr, int l, int r){
    Comparable v = arr[l];

    int j = l;
    for( int i = l + 1 ; i <= r ; i ++ )
        if( arr[i].compareTo(v) < 0 ){
            j ++;
            // Swap array element positions
            swap(arr, j, i);
        }

    swap(arr, l, j);

    return j;
}
   ...

If quicksort is applied to a nearly sorted array, the subarrays after each partition are extremely unbalanced, and it can easily degrade toO(n^2)a time complexity algorithm. We need to optimize the above code by randomly selecting a pivot as the benchmark, which is called the randomized quicksort algorithm. We only need to add the following line before the above code to randomly select an element in the array and swap it with the pivot data.

swap( arr, l , (int)(Math.random()*(r-l+1))+l );

Java example code

Source code package download:Download

QuickSort.java file code:

package example;

/**
* Randomized Quick Sort
 */
public class QuickSort {


    // Perform partition operation on the arr[l...r] part
    // Return p, such that arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
    private static int partition(Comparable[] arr, int l, int r){

        // Randomly select a value as the pivot in the range arr[l...r]
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...j] < v ; arr[j+1...i) > v
        int j = l;
        for( int i = l + 1 ; i <= r ; i ++ )
            if( arr[i].compareTo(v) < 0 ){
                j ++;
                swap(arr, j, i);
            }
        swap(arr, l, j);
        return j;
    }

    // Recursively use quicksort to sort the range arr[l...r]
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){
        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Test QuickSort
    public static void main(String[] args) {

        // Quick Sort is also an algorithm with O(n log n) complexity
        // Can easily handle data on the order of 1 million within 1 second
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Implementation of randomized Quick Sort

Python implementation

Example

import random

def randomized_quick_sort(arr, low=None, high=None):
    """
Main function for randomized quicksort
   
Parameters:
arr: the list to be sorted
low: starting index of the subarray (default 0)
high: ending index of the subarray (default len(arr)-1)
   
Returns:
The sorted list (sorted in place; also returns the sorted list)
    """
    # Set default parameters
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    # Recursion termination condition: subarray length is less than or equal to 1
    if low < high:
        # Randomly select pivot and partition
        pivot_index = randomized_partition(arr, low, high)
       
        # Recursively sort the left and right subarrays
        randomized_quick_sort(arr, low, pivot_index - 1)
        randomized_quick_sort(arr, pivot_index + 1, high)
   
    return arr

def randomized_partition(arr, low, high):
    """
Randomized partition function
   
Parameters:
arr: the list to be partitioned
low: starting index of the subarray
high: ending index of the subarray
   
Returns:
The final position index of the pivot value
    """
    # Randomly select an index as the pivot position
    random_index = random.randint(low, high)
   
    # Swap the randomly selected element with the last element
    arr[random_index], arr[high] = arr[high], arr[random_index]
   
    # Use the last element (which is now the randomly selected element) as the pivot
    return partition(arr, low, high)

def partition(arr, low, high):
    """
Partition function (same as quicksort)
   
Parameters:
arr: the list to be partitioned
low: starting index of the subarray
high: ending index of the subarray
   
Returns:
The final position index of the pivot value
    """
    pivot = arr[high]  # Pivot
    i = low - 1        # Boundary of the region less than the pivot
   
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            # Swap elements
            arr[i], arr[j] = arr[j], arr[i]
   
    # Place the pivot in the correct position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

# Test data
test_data = [3, 6, 8, 10, 1, 2, 1]
print("Original array:", test_data)
print("Sorted array:", randomized_quick_sort(test_data.copy()))

Time complexity analysis

The time complexity of randomized quicksort can be expressed by the following formula:

\[ T(n) = O(n) + T(k) + T(n - k - 1) \]

Where:

  • \( O(n) \) is the time for the partition operation.
  • \( T(k) \) is the time to sort the left subarray.
  • \( T(n - k - 1) \) is the time to sort the right subarray.
  • \( k \) is the number of elements to the left of the pivot value.

In the randomized version, the expected value of \( k \) is \( n/2 \), so the expected time complexity is:

\[ E[T(n)] = O(n \log n) \]

Variants and optimizations of randomized Quick Sort

1. Three-way Quick Sort

When the array contains many duplicate elements, traditional two-way quicksort is not efficient. Three-way quicksort divides the array into three parts: less than the pivot, equal to the pivot, and greater than the pivot.

Example

def randomized_three_way_quick_sort(arr, low=None, high=None):
    """Three-way randomized quicksort"""
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    if low < high:
        # Randomly select the pivot
        random_index = random.randint(low, high)
        arr[random_index], arr[low] = arr[low], arr[random_index]
        pivot = arr[low]
       
        # Three-way partition
        lt = low      # Region boundary for values less than the pivot
        gt = high     # Region boundary for values greater than the pivot
        i = low + 1   # Current element being checked
       
        while i <= gt:
            if arr[i] < pivot:
                arr[lt], arr[i] = arr[i], arr[lt]
                lt += 1
                i += 1
            elif arr[i] > pivot:
                arr[i], arr[gt] = arr[gt], arr[i]
                gt -= 1
            else:
                i += 1
       
        # Recursively sort the partitions less than and greater than the pivot
        randomized_three_way_quick_sort(arr, low, lt - 1)
        randomized_three_way_quick_sort(arr, gt + 1, high)
   
    return arr

# Test with data containing duplicate elements
test_data_with_duplicates = [3, 6, 3, 8, 1, 3, 6, 1]
print("Original array (with duplicates):", test_data_with_duplicates)
print("After three-way quicksort:", randomized_three_way_quick_sort(test_data_with_duplicates.copy()))

2. Small array optimization

For very small arrays (typically fewer than 10-20 elements), insertion sort may be more efficient than quicksort. We can combine the advantages of the two algorithms:

Example

def optimized_randomized_quick_sort(arr, low=None, high=None, threshold=10):
    """Optimized randomized quicksort: use insertion sort for small arrays"""
    if low is None:
        low = 0
    if high is None:
        high = len(arr) - 1
   
    # Use insertion sort for small arrays
    if high - low + 1 <= threshold:
        insertion_sort(arr, low, high)
        return arr
   
    if low < high:
        pivot_index = randomized_partition(arr, low, high)
        optimized_randomized_quick_sort(arr, low, pivot_index - 1, threshold)
        optimized_randomized_quick_sort(arr, pivot_index + 1, high, threshold)
   
    return arr

def insertion_sort(arr, low, high):
    """Insertion sort, used for sorting small arrays"""
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Test the small-array optimization
small_test_data = [9, 3, 7, 1, 5, 2, 8, 4, 6]
print("Original small array:", small_test_data)
print("After optimized sorting:", optimized_randomized_quick_sort(small_test_data.copy(), threshold=5))

Performance comparison and practical recommendations

Performance test

Let us compare the performance of different sorting algorithms through practical tests.

Example

import time
import random as rand

def performance_test():
    """Performance test: compare execution times of different sorting algorithms"""
    algorithms = {
        "Randomized quicksort": randomized_quick_sort,
        "Three-way quicksort": randomized_three_way_quick_sort,
        "Optimized quicksort": optimized_randomized_quick_sort,
    }
   
    # Generate test data
    test_sizes = [100, 1000, 10000]
   
    for size in test_sizes:
        print(f"\nTest array size: {size}")
       
        # Generate different types of test data
        test_cases = {
            "Random data": [rand.randint(0, 10000) for _ in range(size)],
            "Sorted data": list(range(size)),
            "Reversed data": list(range(size, 0, -1)),
            Large amount of duplicate data: [rand.randint(0, 10) for _ in range(size)],
        }
       
        for case_name, test_data in test_cases.items():
            print(f"  {case_name}:")
           
            for algo_name, algo_func in algorithms.items():
                data_copy = test_data.copy()
                start_time = time.time()
                algo_func(data_copy)
                end_time = time.time()
               
                execution_time = (end_time - start_time) * 1000  # Convert to milliseconds
                print(f"    {algo_name}: {execution_time:.2f} ms")

# Run performance test (note: this may take some time for large arrays)
# performance_test()

More code examples

other extensions