Quick Sort (JavaScript)
Quick sorting is a sorting algorithm that focuses on placing a single value of an array in its correct position for each iteration. It does this by splitting the array at a pivotal point (called the pivot), and then moving all numbers greater than that pivot to be after it, and all numbers less than the pivot to be before it.
For example, given the array [3, 7, 4, 5, 9], you might select a pivot point of index 3 (which has a value of 4 in the above array). You would then go through each number and ask “Is it greater than or less than the pivot?”. In the above example, 3 would be less and so remain as-is. 7 would be greater and so be pushed beyond the pivot. 5 and 9 are then both greater and so remain where they are. So what we’re left with is an array of [3, 4, 7, 5, 9], where the pivot number (4) is now in the correct place in the array.
From there, we can then repeat the process on the values either side of the array recursively, until every value in the array is correctly placed.
In my opinion, quick sort isn’t a great method of sorting. There are far too many arbitrary aspects for how your code can work that make it less of an algorithm and more of an idea, and that makes implementation difficult to understand, as everyone has a slightly different method. In addition, it doesn’t resemble any real-life method of sorting, so I find it a little less intuitive than most. That said, most implementations do share key concepts, so if you can learn those, it makes everything a little bit easier.
In addition, although not my favourite in terms of how it works, what I do like is that it performs the sorting operation in-memory, something you may sometimes be asked to do specifically.
Below are two similar but different methods of implementing quick sort in JavaScript. Both follow the same pattern; we choose a pivot, split the array in 2 (one side with values less than the pivot, the other side with values greater than it), and then repeat the process for each part, until we eventually have a sorted array. Both also have the same final step; after sorting the non-pivot contents of the array, we then place the pivot in between both sides, so as to “correctly” place it.
Method #1: For loop
In this method, we make our pivot our right-most element (so as to make the for loop more readable, as it can still go left-to-right). Then we loop through all of the elements in the array, and move those lower than the pivot to the left hand side, and those greater than it to the right hand side. Finally, we place the pivot in the middle of all these numbers (technically, we swap it for the lowest number that is greater than the pivot), and we have then found the correct placement for the pivot.
This method was inspired by this great video from mycodeschool, which I recommend you check out once you grasp the above.
Method #2: While
In this method, we make our pivot the left-most element. Next we place markers at the next element in the array, and the final element of the array. Now, we move the left-marker right until we find a value that is greater than the pivot, and we move the right-marker left until we find a value that is lower than the pivot. In other words, we constrict the window of observation until we find numbers that belong on the opposite sides. Then we swap these values, so that they are now on the correct sides, and then continue until our markers meet. Finally, we place the pivot in the middle of all these numbers, and we have then found the correct placement for the pivot.
This method was inspired by this great video from Abdul Bari, which I recommend you check out once you grasp the above.