The next intermediate sorting algorithm we'll discuss is Quick Sort. The general idea of Quick Sort is to choose a "pivot" point for comparison, and this can be any item in the array. Then what we do is compare the other values to that and smaller ones get placed to the left and larger ones you guessed it get placed to the right. Once completed we can now assume that our pivot point is in the right place of the array. So we break down our initial array into 2 arrays based on their values being larger or smaller than our selected pivot value. Then in these newly formed arrays we select a new "pivot" point and we repeat the process. As you guessed it since we are repeating over and over again the best way to do this would be to use recursion, and again completely understanding this one gets very tough very fast. It is much harder to conceptualize it than Merge Sort (in my opinion). Ideally you should use the same pivot index in each call, I like to use the first or last element of the array however you can use any. Here is a quick visualization of how this algorithm works.
.
Similarly to MergeSort we'll need to create a helper function so that we can do the comparisons with out pivot value and the array that is passed in. This pivot helper should accept three values, an array, a start index, and and an end index. Well then grab the pivot point from the start of the array, and again you can choose any point I'll just use the beginning for consistencies (ideally you'd choose the median value, however you might not know it so this will work, in fact any position will work). We will then loop through the array from the start to end index and compare our pivot value (index of 0) to the next value. If that value is greater we need to swap those 2 values and increase the pivot index, which for use will be 0 by 1. At the end of this function we'll return the pivot index.
So after watching videos over and over again and reading many different posts about Quick Sort I can 100% say that I just don't understand it. I can 100% talk about it and how it works but if anyone ever asked me to implement it from scratch I'd be in some serious trouble. I feel like with Merge Sort I could rebuild it based on just being able to talk about it where with this algorithm, I just cannot break it down to a point where it makes sense to me. So for you it might but I got nothing. I'm gonna keep trying and if I somehow manage a breakthrough with this I will definitely come back and revisit this post. But my interview with the big "G" is happening Wednesday and I cannot take time that I don't have to try and learn this particular concept better. QuickSort
Top comments (0)