DEV Community

Toni Domazet
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]) 

Enter fullscreen mode Exit fullscreen mode

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];
Enter fullscreen mode Exit fullscreen mode

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)];
Enter fullscreen mode Exit fullscreen mode

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.


alt text

Top comments (0)