YouTip

## Randomized Quick Sort Quick Sort is one of the most classic sorting algorithms in computer science, known for its average time complexity of O(n log n). However, when the input data is already sorted or nearly sorted, the traditional Quick Sort degrades to O(n²) time complexity. Randomized Quick Sort cleverly solves this problem by introducing randomness. Before diving into Randomized Quick Sort, let's review the core idea of traditional Quick Sort. ### How Quick Sort Works Quick Sort uses the **divide and conquer** strategy, with the following basic steps: 1. **Select a pivot**: Choose an element from the array as the pivot 2. **Partition operation**: Rearrange 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. **Recursive sorting**: Recursively apply the same process to the subarrays on both sides of the pivot ### Problems with Traditional Quick Sort The performance of traditional Quick Sort highly depends on the pivot selection. The algorithm is most efficient when each pivot divides the array into roughly two equal parts. However, performance degrades significantly in the following cases: * **Sorted array**: If the array is already sorted, selecting the last element as the pivot each time leads to extremely unbalanced partitions * **Reverse sorted array**: Similar to sorted array, but in the opposite direction * **Duplicate elements**: A large number of duplicate elements can also cause unbalanced partitions In these worst-case scenarios, Quick Sort's time complexity degrades to O(n²), comparable to simple algorithms like Bubble Sort. Randomized Quick Sort introduces randomness to avoid worst-case scenarios, ensuring the algorithm maintains good average performance across various inputs. The core improvement of Randomized Quick Sort is very simple: **randomly select the pivot**, instead of always choosing the first, last, or middle element. This randomness makes the probability of worst-case scenarios extremely low, guaranteeing an expected time complexity of O(n log n). **Basic idea of Randomized Quick Sort:** Through one pass of sorting, divide the data to be sorted into independent two parts, where all data in one part is smaller than all data in the other part. Then apply Quick Sort to these two parts separately using the same method. The entire sorting process can be done recursively, thereby making the entire data an ordered sequence. !(#) ### Algorithm Advantages | Feature | Traditional Quick Sort | Randomized Quick Sort | | --- | --- | --- | | Worst-case time complexity | O(n²) | O(n²) (but extremely low probability) | | Average-case time complexity | O(n log n) | O(n log n) | | Worst-case occurrence condition | Specific input (e.g., sorted array) | Random selection always picks extreme values | | Space complexity | O(log n) (recursion stack) | O(log n) (recursion stack) | | Stability | Unstable | Unstable | Although the theoretical worst-case time complexity of Randomized Quick Sort is still O(n²), in practical applications, the probability of this worst case occurring is extremely low. For an array containing n elements, the probability of random pivot selection leading to worst case is approximately 1/n!, which is virtually impossible to occur in practice. ### Process Illustration Select a pivot point in an array, for example, the 4 at the first position, then move 4 to its correct position so that data in the subarray before it is less than 4, and data in the subarray after it is greater than 4. Then recursively proceed to complete the entire sorting. !(#) How to move the selected pivot data to its correct position is the core of Quick Sort, which we call Partition. The process is as follows, where i is the position of the current element being compared: !(#) This partition process expressed in code is: ## Examples ... private static int partition(Comparable[] arr, int l, int r){ Comparable v = arr; int j = l; for(int i = l +1; i <= r ; i ++) if( arr.compareTo(v)<0){ j ++; //Swap array element positions swap(arr, j, i); } swap(arr, l, j); return j; } ... If performing Quick Sort on a nearly sorted array, after each partition, the subarray sizes are extremely unbalanced, easily degrading to O(n²) time complexity. We need to optimize the above code by randomly selecting a pivot point for comparison, which is the Randomized Quick Sort algorithm. Simply add the following line before the above code to randomly select an element from the array and swap it with the pivot. swap( arr, l , (int)(Math.random()*(r-l+1))+l ); ### Java Example Code **Source Package Download:*## QuickSort.java File Code: package tutorial; /** * Randomized Quick Sort */ public class QuickSort { // onarr[l...r]Perform partition operation on the portion // Returnp, Make arr[l...p-1] arr private static int partition(Comparable[] arr, int l, int r){ // Randomly in arr[l...r]in the range of, Select a value as the pivot point swap( arr, l , (int)(Math.random()*(r-l+1))+l ); Comparable v = arr; // arr[l+1...j] v int j = l; for(int i = l +1; i <= r ; i ++) if( arr.compareTo(v)= 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; arr= arr; arr= t; } // Test QuickSort public static void main(String[] args){ // Quick Sortalsois an algorithm with O(nlogn) complexity // Can easily handle data on the scale 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 ## Examples import random def randomized_quick_sort(arr, low=None, high=None): """ Main function of randomized quick sort Parameter: arr: List to be sorted low: Start index of the subarray (default is 0) high: End index of the subarray（defaults to len(arr)-1) Return: sorted list (in-place sort, also returns the sorted list) """ # Set default parameter 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 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): """ Random partition function Parameter: arr: List to be partitioned low: Start index of the subarray high: End index of the subarray Return: Final position index of the pivot """ # Randomly select an index as the pivot position random_index =random.randint(low, high) # Swap the randomly selected element with the last element arr, arr= arr, arr # Use the last element (now the randomly selected element)