Published Nov 23 2020

Psssst! The 2023 WEB DEVELOPMENT BOOTCAMP is starting on FEBRUARY 01, 2023! SIGNUPS ARE NOW OPEN to this 10-weeks cohort course. Learn the fundamentals, HTML, CSS, JS, Tailwind, React, Next.js and much more! ✨

Quicksort is a more efficient searching algorithm than selection sort, *in most cases*, and it makes use of recursion.

Recursion means we call a function from within the same function. It’s a very useful practice, sometimes, and this is one of those cases.

I said “in most cases”, because as we’ll see, in the worst case bubble sort can take the same time of selection sort: `O(n^2)`

. But in the best case scenario, it will run at `O(n log n)`

, which is in the middle between `O(n)`

and `O(n^2)`

.

How does it work? Given an array, we pick an item, called *pivot*. We then get all the items smaller than the pivot, and the items bigger than the pivot.

Then we run the same operation on the 2 array that compose the smaller and bigger items.

It’s easier to see the code than to describe it:

```
const quickSort = (originalList) => {
const list = [...originalList]
if (list.length < 2) {
return list
}
const pivot = list[0]
const smaller = list.filter((item) => item < pivot)
const bigger = list.filter((item) => item > pivot)
return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}
```

In this case I chose the pivot to be the first item in the array, but it could also be the item in the middle, for example:

`const pivot = list[Math(floor(list.length / 2)]`

Notice how we first copy the array, so calling `quickSort()`

does not modify the original array, it just returns a new sorted array:

```
const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]
console.log(quickSort(a))
//[0, 1, 1, 3, 4, 4, 5, 6, 8
console.log(a)
//[1, 6, 3, 4, 5, 1, 0, 4, 8]
```

© 2023 Flavio Copes made in Italy 🇮🇹 using
Notion to Site