Toni Domazet

Posted on

# Quicksort sorting algorithm

Quicksort is a sorting algorithm. It's a divide-and-conquer algorithm that sorts a sequence by recursively dividing it into smaller subsequences. Let's see our function:

``````function quick_sort(array) {
if(array.length < 2) return array;

const pivot = array[0];

let lower = array.filter(e => e < pivot),
greater = array.filter(e => e > pivot);

return [...quick_sort(lower), pivot, ...quick_sort(greather)];
}

quick_sort([7,5,9,4,8,2])

``````

Empty arrays and arrays with just one element are the base case. Nothing to sort here, and we can just return those arrays as is.

Quicksort algorithm starts with picking a pivot. There are many ways to choose a pivot:
• 1st element (as we do)
• last element
• median of the array as a pivot
• a random element as the pivot

``````const pivot = array[0];
``````

After filtering collection (array) we have:
• A sub-array of all the numbers lower than the pivot
• The pivot
• A sub-array of all the numbers greater than the pivot

``````return [...quick_sort(lower), pivot, ...quick_sort(greater)];
``````

Call quicksort recursively on the two sub-arrays (lower and greater) to break down the collection into single-element lists (hitting the base case), before combing them into one sorted list.

Here are all the steps (stack) depending on pivot we pick.