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

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.


alt text

Top comments (0)

Let's Get Wacky


Use any Linode offering to create something unique or silly in the DEV x Linode Hackathon 2022 and win the Wacky Wildcard category

Join the Hackathon <-