Most discussions about sorting algorithms tend to end up discussing quicksort because of its speed. Formal computer science programs also tend to cover quick sort last because of its excellent average complexity of O(nlogn) and trelative performance improvement over other less efficient sorting algorithms such as bubble sort and insertion sort for large data sets. Unlike other sorting algorithms, htere are many different implementation of quicksort that lead to different performance characteristics and whether or not the sort is stable(with equivalent items remaning in the same order in which they naturally occurred).

Quicksort is a divide and conquer algorithm in the style of merge sort. The basic idea is to find a "pivot" item in the array to compare all other items against, then shift items such that all of the items before the pivot are less than the pivot value and all the items after pivot are lar greater than the pivot value. After that, recursively peform the same operation on the items before and after the pivot. There are many different algorithms to achieve a quicksort.

There are two basic opertions in the algorithm, swapping items in palce and partitioning a section of the array. The basic steps to partition an array are:

  1. Find a 'Pivot' items in the array. This item is the basis for comparison for a single round. Because of if we select the first item as pivot gives worst-case performance on already sorted arrays. Ite's better to select a pivot in teh middle of the array.
  2. Start a pointer(the left pointer) at the first item in the array.
  3. Start a poniter(the right pointer) at the end item in the array.
  4. While the value at the left pointer in the array is less than the pivot value, move the left pointer to the lright(add 1), continue until the value at the left pointer is greater or equal to the pivot value.
  5. While the value at the right pointer in the arry is greater than the pivot value, move the right pointer to the lfet(subtract 10. Continue until the value at the right pointer is less than or equal to the pivot value.
  6. If the left pointer is less than or equal to the right pointer, then swap the values at these locations in the array.
  7. Move the left pointer to the right by one and the right pointer to the left by one.
  8. If the left pointer and right pointer don't meet, go to step 1.

original address https://humanwhocodes.com/blog/2012/11/27/computer-science-in-javascript-quicksort/

function swap(items, leftIndex, rightIndex) {
    const temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    if(!items.length) {
        return 0;
    }

    const pivot = items[Math.floor((left + right) / 2)];
    let i = left, j = right;
    while(i <= j) {
        while(items[i] < pivot) {
            i++;
        }
        while(items[j] > pivot) {
            j--;
        }
        if( i<=j ) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    console.log('quickSort:' + items);
    if(items.length > 1) {
        const index = partition(items, left, right);
        if(left < index - 1)
            quickSort(items, left, index - 1);
        if(index< right)
            quickSort(items, index, right);  
    }

    return items;
}

let items = [1, 3, 2, 5, 4, 7, 0]
items = quickSort(items, 0, items.length - 1);
console.log(items);