Quick Sort
The advantages of quick sort!
You might be wondering why would I want to use quick sort versus other sorting algorithms? Well as the name suggests, this algorithm is quick! Quick sort is usually quick and usually faster compared to some of the other sort methods but there are some downsides to everything, which means there are downsides to quick sort!
The disadvantages of quick sort!
Now one of the disadvantages of quick sort is that it is recursive, and the implementation can be frustrating and complicated. Another disadvantage of quick sort is that it can be easily broken and causing it to not perform correctly or badly with the issue being unnoticeable. Overall, quick sort is a good sorting method to use though once you get the hang of it! There are also different sorting methods so be sure to try and select the ones that you think best will work with what you are trying to accomplish instead of relying on just quick sort!
Quick Sort Recursive
In quick sort when we have an array that calls for a quick sort to be recursive, we need to do some partitioning. A quick way to think of partitioning is that we have an element that we use to sort numbers being greater or less than that element. We then will have an array with an element that should be in the position where it needs to be but have to rearrange (sort) the numbers on the left and right of this index by calling the quick sort function again on those. Don’t worry we will go over examples.
Partitioning Overview
One of the things you need to do in Quick Sort is called “partitioning”. There are also many different ways to partition an array, I will be going over just one of the ways. To partition an array, you have a “pivot” which is usually the last element of the array. This pivot or element that we selected will be used to compare other numbers in the array and rearrange them. Any number that is less than the pivot we will move to the left side of the array while the right side are numbers that are greater than the pivot.
Counters
We will have two counters going on during quick sort, them being ‘L’ and ‘R’. We will have ‘L’ set to one less than the start of the array and will set ‘R’ to the first element of the array. Our ‘R’ counter iterates from the start of the array to one less than the last element (the pivot).
Partitioning Process
During the partitioning process we start with counter ‘R’ that is at the first element then compares it with the pivot that we have selected. If ‘R’ is greater than our pivot, then we do nothing and move onto the next number. If the number is less than our pivot, then we increment ‘L’ and swap the element that is at ‘L’ with the element that is at ‘R’ and then we move on to the next element and do the same thing until we hit the element that is second to last. Once we get to the end, we then have the pivot put at the position of ‘L’ + 1 meaning that the pivot is now placed in front of the last number that it is greater than.
Example Time
Let’s take a look at an example!
Starting Array [8, 2, 3, 7, 1, 4, 5]This is the array that we be quick sorting
[8, 2, 3, 7, 1, 4, 5]
^ ^ ^
L R PivotSetting our counters. We have L that is currently pointing before the first element of the array, R set to the first element of the array, and our Pivot is at the last element of the array.
[8, 2, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot R > Pivot
8 > 5
We will then compare the value of R to the Pivot which in this case we would check if 8 is greater than 5. If R is greater than the Pivot, R will increment to the next element and compare again.
[8, 2, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot R > Pivot
2 > 5
The next element gets compared to the Pivot, in this case it’s comparing if 2 is greater than 5. We obviously know that this is false and in that case we would do the following.
[8, 2, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot
R > Pivot
2 > 5[8, 2, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot 8 <-> 2 SWAP![2, 8, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot
Let’s breakdown what just happened!
- We compared if 2 > 5, which it is not so then we would have L increment by one by L + 1. Meaning L now points to the value of 8
- We then swapped the value of the element that was at L and R meaning we swapped 8 to where 2 was and vice versa.
- We then move onto the next value
[2, 8, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot R > Pivot
3 > 5[2, 8, 3, 7, 1, 4, 5]
^ ^ ^
L R Pivot8 <-> 3 SWAP![2, 3, 8, 7, 1, 4, 5]
^ ^ ^
L R Pivot
Currently R is less than our Pivot so we would do the same thing again!
- We compared if 3 > 5, which it is not so then we would have L increment by one by L + 1. Meaning L now points to the value of 8 again
- We then swapped the value of the element that was at L and R meaning we swapped 8 to where 3 was and vice versa.
- We then move onto the next value
[2, 3, 8, 7, 1, 4, 5]
^ ^ ^
L R Pivot R > Pivot
7 > 5
We will again compare the value of R to the Pivot which in this case we would check if 7 is greater than 5. If R is greater than the Pivot, R will increment to the next element and compare again.
Okay, I think we all get the point so let me just skip to the end so we can talk about what happens after R goes all the way through the array.
[2, 3, 1, 4, 8, 7, 5]
^ ^ ^
L R PivotSo once we get to this point we then will have to arrange or pivot into the array.
[2, 3, 1, 4, 8, 7, 5]
^ ^ ^
L R Pivot 5 <-> 8 SWAP![2, 3, 1, 4, 5, 7, 8]
We then swap our Pivot with our L + 1 to be able to get it into the spot where it need to be! If we take a look at the new array, we have numbers less than our pivot on the left and on our right we have numbers higher than our pivot. Hold on, we aren’t done yet! Our numbers aren’t sorted in order from smallest value to greatest. This is where the recursive part of quick sort comes in.
[2, 3, 1, 4, 5, 7, 8]
^---------^ ^--^
Less than pivot Greater than pivotWe have 2 parts we need to sort, however as you can see the one on the right is already sorted so we don’t have to worry about that! However, for the ones on the left we would have it sort through that by the same way we did the original array until we get it all sorted.
[1, 2, 3, 4, 5, 7, 8]Conclusion
I will add onto the blog post or create a new one about the actual function and how to do it once I practice it more!
