Quick Sort Algorithm Implementation in JavaScript

Use Case:

The Quick Sort algorithm is similar to Merge Sort in that it divides the dataset into smaller, more manageable datasets and sorts them before combining and returning.

Here's a description from Wikipedia:

Below we're going to implement the Quick Sort algorithm in JavaScript.

1. Swap Elements Function

The Quick Sort algorithm will require 2 helper functions and the first will help us to swap 2 items in the dataset.

swap = (array, i, j) => {
	var temp = array[i]
	array[i] = array[j]
	array[j] = temp	  
}

The swap function will accept the dataset as an array and 2 index values, and then swap the values at the 2 indexes.

2. Partition Function

partition = (array,low,high) => {
	var pivot = array[Math.floor((high + low) / 2)],
			i = low,
			j = high

	while (i <= j) {
		while (array[i] < pivot) { i++ }
		while (array[j] > pivot) { j-- }
		if (i <= j) {
			swap(array,i,j)
			i++
			j--
		}
	}
	return i
}

The partition function accepts our dataset as an array and 2 values, low and high. First, it determines a pivot value to use for comparison based on the value of high plus low divided by 2. Then it sets the values of i and j for simplicity.

Then we'll loop for as long as i isn't greater than j. While looping, we'll perform 2 internal loops. The first will increment i every time a value is found that it less than the pivot value. The second loop will decrement j every time a value is found that is greater than the pivot value.

After the loops are complete, if i is still not greater than j, then we'll call the swap function sending in the array and the 2 values and increment/decrement the values 1 more time. Finally, we'll return the value of i.

A good explanation with a visual of this process can be found here.

3. Quick Sort Function

quickSort = (array,low,high) => {
	var low = (low) ? low : 0,
			high = (high) ? high : array.length - 1,
			index
	if (array.length > 1) {
		index = partition(array,low,high)
		if (low < index - 1) { quickSort(array,low,index - 1) }
		if (index < high) { quickSort(array,index,high) }
	}
	return array
}

The quickSort function will accept an array of our dataset and values for low and high. Since I like to make things easy for myself later on, to make this function easier to call you can do so with just an array value since we'll set the values of low and high if not already set. We'll also declare an index variable.

Then we'll verify that our dataset is larger than 1, and set our index equal to the returning value from the partition function when the array and low and high values are passed into it.

If the value of low is less than the index value minus 1, then we'll recurse the quickSort function. Additionally, we'll recurse it again if the index value is less than the value of high.

Finally, we'll return our sorted array.

Results

var array = [8,3,5,9,1,5,9,2,3,8,4]
quickSort(array)
//4,3,5,9,1,5,9,2,3,8,8
//4,3,3,9,1,5,9,2,5,8,8
//4,3,3,2,1,5,9,9,5,8,8
//4,3,3,2,1,5,9,9,5,8,8
//1,3,3,2,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,9,9,5,8,8
//1,2,3,3,4,5,5,9,9,8,8
//1,2,3,3,4,5,5,8,9,8,9
//1,2,3,3,4,5,5,8,8,9,9
//1,2,3,3,4,5,5,8,8,9,9
//1,2,3,3,4,5,5,8,8,9,9

Quick Sort is a generally efficient sorting algorithm. Its worst case time complexity is O(n^2) which is similar to other less efficient algorithms such as the Bubble and Insertion sorts, but its average time complexity is actually Θ(n log n) which puts it on par with Merge and Heap sorts. It's at its worst in datasets with many of the same values.

Since it is dividing the dataset into smaller sets, its space complexity isn't O(1) but rather can be measured at O(log n) which is still considered efficient (and better than Merge Sort).

Also, it isn't a stable sorting algorithm as equal values are likely to be moved and not retain their indexed order.

Check out other sorting algorithm implementations in JavaScript:

• Merge Sort
• Selection Sort
• Shell Sort
• Radix Sort
• Heap Sort
• Bubble Sort
• Insertion Sort