Quick Sort with Swift

This time on SwiftyAlogs we will be taking a look at the classic sorting algorithm Quick Sort. Similar to Merge Sort, Quick Sort works based on the idea of split and tackle. Quick Sort relies on choosing some element, known as a pivot, and then segmenting or partitioning the collection to be sorted around that pivot. Quick Sort is a very flexible way to sort; allowing for the pivot to be declared in a number of ways:

• Pivot on the first element
• Pivot on the last element (this is the one we will use)
• Pivot on a random element
• Pivot on the median element

The critical part of the Quick Sort process is the partition…

A partition works based on the following idea: If we have an array of things, and we choose a pivot . . .

1. place the pivot in the correct position in the array
2. move all things smaller before the pivot
3. move all things larger after the pivot

The resulting two sides of this operation all called partitions, within each of these we can recursively repeat the process until we reach a point where our partitions are too small to sort, and we should ultimately have a sorted array.

It works like this…

So, starting with an unsorted array…

1. First we take the last element as our pivot.
2. Next we assign i and j to track indexes. j = 0, and i = j-1 to start with.
3. From here we compare j with the pivot. If the pivot is less than the value of j, we move on, incrementing j+1. If the value of j is greater than the pivot, we swap the pivot with j and increment both j+1 and i+1.
4. Now we compare values again, if the j is less than the pivot, we will increment i+1, and swap the values at j and i.
5. Next increment j+1, and do it all again, compare to the pivot, swap or not, and move on.
6. Once we reach the last element in the array (the one right next to the pivot), we compare those two values, IF the value is less than the pivot then the pivot stays put, and we partition below it.

This can be tricky to understand at first, here is a great video on youtube that explains it with cups, and here is another one that uses dancing Hungarians.

Lets take a look at the code…

And run it…

Check out the code here on Github

Closing thoughts…

Quick Sort is comparatively one of the more challenging algorithms that we have looked at in this series thus far, but with a little practice it should become clear. I would strongly encourage you to take it to paper if you are a bit confused, start with a smaller set of values, and write it out; this certainly helped me to understand things a bit better. One of the best things in my opinion about Quick Sort is how flexible the concept is, there a many different ways to approach it and many ways to implement it! If you’re interested in digging deeper on this I would encourage you to head over to The Swift Algorithm Club and check out their deep dive. Thanks again to GeeksForGeeks for providing a great resource for learning CS concepts. As usual it’s important to remember that when you explain an idea you take the greatest steps towards mastery.

Until next time …