Explain how QuickSort works

Technology CommunityCategory: SortingExplain how QuickSort works
VietMX Staff asked 3 years ago

Quick Sort is a divide and conquercomparisonin-place algorithm. Efficient implementations of Quicksort are not a stable sort. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

Quicksort determines something called a pivot, which is a somewhat arbitrary element in the collection. Using the pivot point, quicksort partitions (or divides) the larger unsorted collection into two, smaller lists. It moves all the elements smaller than the pivot to the left (before) the pivot element, and moves all the elements larger than the pivot to the right (after) the pivot element. Even though the list isn’t completely sorted yet, we know that the items are in the correct order in relation to the pivot. This means that we never have to compare elements on the left side of the partition to elements on the right side of the partition. We already know they are in their correct spots in relation to the pivot. The sub-lists are then sorted recursively.

Ideally, partitioning would use the median of the given values (in the array), but the median can only be found by scanning the whole array and this would slow the algorithm down. In that case the two partitions would be of equal size; In the simplest versions of quick sort an arbitrary element, typically the last (rightmost) element is used as an estimate (guess) of the median.

Complexity Analysis

Overall time complexity of Quick Sort is O(n log n). In the worst case, it makes O(n2) comparisons (all elements are same or array is already sorted).

The partition step used in quicksort ideally is an in-place operation (without creating any additional arrays). But since quicksort calls itself on the order of log(n) times (in the average case), worst case number of calls is O(n), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log n) space complexity.

Implementation

With additional memory (naive):

function quickSort (arr) {
    if(arr.length <= 1) return arr;

    // find middle point of array (effectively random pivot) 
    var swapPosition = Math.floor((arr.length -1) / 2);
    var pivot = arr.splice(swapPosition, 1);
    var left = [];
    var right = [];

    for(var i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i])
        }
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

In-place:

var quickSort = function(array, left, right) {

    var leftIndex = partition(array, left, right);

    if (left < leftIndex - 1) {
        quickSort(array, left, leftIndex - 1);
    }

    if (right > leftIndex) {
        quickSort(array, leftIndex, right);
    }

    return array;
}

var swap = function(array, left, right) {
    var temp;
    temp = array[leftIndex];
    array[leftIndex] = array[rightIndex];
    array[rightIndex] = temp;
}

var partition = function(array, left, right) {
    var pivotIndex = Math.floor((left + right) / 2);
    var pivot = array[pivotIndex];

    leftIndex = left;
    rightIndex = right;

    while (leftIndex <= rightIndex) {
        while (array[leftIndex] < pivot) {
            leftIndex++;
        }

        while (array[rightIndex] > pivot) {
            rightIndex--;
        }

        if (leftIndex <= rightIndex) {
            swap(array, left, right);
            leftIndex++;
            rightIndex--;
        }
    }
    return leftIndex;
}