Searching and Sorting Algorithms in Javascript — Part 6 (Quick Sort)
Quick sort is one of the “more advanced” sorting algorithms out there. It is very efficient and scale well for fairly large arrays. Of all these “more advanced” algorithms, quick sort just somehow doesn’t sit very well with me (using the words of my mentor: “my brain just doesn’t like the way quick sort works”). It’s just something I can’t always work with out of the box. I have to consult several materials every single time I want to use it or work with it.
Well, I believe you’re smarter than me so, you’ll understand pretty well. Let’s get into it…
I mean, what is this big guy made of ? 🙄
I will try to explain in words, show you some illustration then show you how the code works.
In words…
It follows the basic idea that merge sort use which is that: “An array that contains a single element is already sorted”… and that’s the only similarity between Merge sort and Quick sort.
Quick sort starts by picking an element in your array and puts that element in the right position. It does this by moving everything greater than the current element to the right of that element and everything less than it to the left of that element.
I’m sure you’re curious, what’s so hard about it then? Well, Quick sort doesn’t end there… Remember I said quick sort works by picking an element? Well, after putting that element in it’s right position, it then does the following:
1. Sort the left side of our current element using the same algorithm.
2. Sort the right side of the current element using the same algorithm.
An Illustration…
So say we have an array with elements [4, 5, 2, 1, 3]. Quick sort starts by taking 4 (the number at the beginning of the array) and put it in the right position. The way that works is this:
- It takes 4, loops through every element to right of 4 and compare 4 to each element.
- If that number is lesser than 4, it has to end up somewhere at the left of 4. It doesn’t try to sort the left yet, it just makes sure that every number to the left of 4 is lesser than 4 and every number to the right of 4 is greater than 4.
To elaborate on point 2, let’s go through each pass on the loop.
- First Pass — the algorithm compares 4 and 5 and checks: “is 4 greater than 5?”. The answer is “NO” so it doesn’t do anything.
- Second Pass — the algorithm compares 4 and 2 and checks: “Is 4 greater than 2?”. The answer is “YES” so, it swaps 2 and 5 (Yes, 2 and 5. Not 2 and 4). We now have [4,2,5,1,3] as our new array. You might still be thinking of the swap we made in this step so , let me take my time to explain properly.
The aim of the algorithm is to record all the numbers lesser than 4, push them close to each other. At the end of the loop, the algorithm then swap 4 with the last element smaller than 4. I still don’t expect it to make sense at this point but, It will. Just hold on tight - Third Pass — the algorithm compares 4 and 1 and checks: “Is 4 greater than 1?”. The answer is Yes so, it swaps 1 and 5. So, we now have [4,2,1,5,3] as our new array. (Note that the algorithms has been putting every element less than 4 it has encountered behind the first thing it encountered that was greater than it which is 5 in this case ).
- Fourth Pass — the algorithm compares 4 and 3 and checks: “Is 4 greater than 3?” The answer is YES so, it swaps 3 and 5. Now we have [4,2,1,3,5] as our new array. The loop has come to an end at this point and 3 was the last element recorded that is smaller than 4. The algorithm then swaps 4 and 3. Now we have [3,2,1,4,5] as our new array.
You’ll realize that at this point, every element to the left of 4 is lesser than 4 and every element to right of 4 is greater than 4.
It then takes a sub-array that contains all element to the left of 4 and repeats the same process until the sub-array is totally sorted. After that, it takes another sub-array that contains all element to the right of 4 and repeats the same process until the sub-array is totally sorted.
In Code…
I hope the code does explains itself. Please, try to go over this article over and over again until it sits right with you.
How efficient is this algorithm?
This algorithm has an average time complexity of O(n log n) and a worst case time complexity of O(n²). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element.
Overall it’s very efficient (most times more efficient than Merge sort) but I personally usually prefer merge sort (because it’s easier to implement than this guy).
I hope that helps, see you on the next one… 👍
