Algorithms Visualized
Quick Sort
The Quick Sort algorithm uses a Divide and Conquer strategy for sorting an array of items. Divide and Conquer is a technique that can be divided into the following three parts:
- Divide the problem into two or more sub-problems of the same or related type
- Conquer the sub-problems by calling recursively until all the sub-problems are solved
- Combine the solutions to the sub-problems are then combined to give a solution to the original problem.
Here is the plan for a quick sort implementation in JavaScript.
First, pick a pivot element in the array. The pivot element should be the element that is as close to the middle of the array as possible.
Second, rearrange the array elements so that all elements smaller than the pivot element move to left side of of the pivot, and all greater elements move to right side of the pivot.
Third, recursively sort the subarrays on left and right of pivot element.
Let’s look at some code.
Line 50: populate a random unsorted array named unsortedArray.
Line 54: set a const to the lowest index (lowIndex) in the the array passed in, in this case 0.
Line 57: set a const to the highest index in the array (highIndex). In this case this value will be 5, because the array has 6 elements.
Line 61: call the quickSort function, passing in the array along with lowIndex and highIndex.
Next, have a look at the quickSort function.
Line 3–7: swap is a helper function that swaps items in the targetArray, based on the lowIndex and highIndex values, swapping the values at the indexes. It is used later in the quickSort function.
Line 10: This is where the midpoint, or pivot, in the array is determined. The value of pivotElement after line 10 executes (the first time) is 2, the element closest to the middle of the array:
[7, 0, 2, 1, 9, 2]Line 13: Set a variable, leftPointer to the value of the lowIndex passed, in this case 0.
Line 16: Set a variable, rightPointer to the value of the highIndex passed, in this case 5.
Lines 19–35: This is where the magic happens. The array elements are rearranged so that all elements smaller than the pivot element move to left side of of the pivot, and all greater elements move to right side of the pivot. The swap function is used to move elements from left of the pivot to the right and vice-versa.
Line 35: the values of the variables are as follows (after the first time through).
targetArray = [2, 0, 1, 2, 9, 7]
(all values lower than 2 are left of 2 and all values larger than 2 are on the right of 2)lowIndex = 0
highIndex = 5leftPointer = 3
rightPointer = 2
(the leftPointer has passed the rightPointer)
Remember, the quickSort function is going to be called recursively.
Line 37–48: The quicksort function is called recursively in order to sort the subarrays on left and right of pivot element.
Line 47: the targetArray is returned, fully sorted.
[0, 1, 2, 2, 7, 9, 2]Why is it important to understand different methods of array sorting such as quick sort? Why not just use the built in array.sort() method in JavaScript?
Under the hood, the built in JavaScript array.sort() method, is actually implemented using different sorting algorithms based on the browser the client is using. Here is a stack overflow post discussing the differences.
The built in sort() uses Insertion sort in V8 Engine of Chrome and Merge sort in Mozilla Firefox and Safari.
There is a great animation of different sorting algorithms here. It can be seen that the quick sort algorithm performs faster than the insertion or merge sort.
