Alg.8 Quick Sort

From algoexpert.io

Quick Sort is a widely-used sorting algorithm, it borrows the strategy, “Divide and Conquer”, to divide the original array into 2 parts and do the sorting recursively. Here are the steps of Quick Sort:

1. Select a pivot, there are a lot of strategies to pick a pivot in order to make sure we can seperate the original array evenly. But here, we simply pick the first elements as pivots

2. Divide the original array into 2 parts, each element of the first one is less than or equals pivot, each element in the second one is greater than pivot

3. Repeat 1 and 2 on the subarrays

private static void quickSortHelper(int[] array, int startIndex, int endIndex) {

        if (startIndex >= endIndex) return;
        
        int pivot = array[startIndex];
        int left = startIndex + 1;
        int right = endIndex;
        while (right >= left) {
            if (array[left] > pivot && array[right] < pivot) {
                swap(array, left, right);
                left++;
                right--;
            }
            
            if (array[left] <= pivot) left++;
            
            if (array[right] >= pivot) right--;
        }
        swap(array, right, startIndex);
        
        // Here's a optimization: In order to run faster, we always want run the subarray
        // with shorter length, therefore, the memory of call stack will be released.
        if (right - 1 - startIndex < endIndex - right - 1) {
            quickSortHelper(array, startIndex, right - 1);
            quickSortHelper(array, right + 1, endIndex);
        } else {
            quickSortHelper(array, right + 1, endIndex);
            quickSortHelper(array, startIndex, right - 1);
        }
        
}

public static int[] quickSort(int[] array) {
        quickSortHelper(array, 0, array.length - 1);
        return array;
}

Since we do the sorting recursively, the space complexity is O(logn)

For the time complexity, if we can’t seperate the arrays evenly, under its worst condition, the time complexity will be O(n^2). However, under its best and average conditions, the time complexity will be O(logn).

Donate