Quick Sort and Bubble Sort in JavaScript

Quick Sort and Bubble Sort are two common types of sorting algorithms used in computer programming, but what exactly are they?

Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Bubble Sort works by repeatedly swapping the adjacent elements if they are in wrong order.

Quick Sort

The above definition is a bit confusing, check out this video for more information on quick sort algorithms. First let’s make a simple function to swap two numbers:

We will work with the following array: const arr = [2,9,4,5,1,6,3,7]. The first step involved in quick sorting is dividing the array to sort into 2 parts, above and below the “pivot” point. We pick a pivot point (usually the middle) and compare each value of the array to it in order to create an array that is larger than the pivot on one side and smaller than the pivot on the other.

To do so we set two counters, left and right, one pointing to the first element in the array the other pointing to the last.

Then compare element at the left pointer with the pivot element. Since 2 < 5 shift the leftpointer to the right to index 1.

Now 9 > 5 so stop incrementing the left pointer, the left pointer is at index 1.

Now we move on to the right counter. Compare the value at the right counter with the pivot element. Since 7> 5 move the right pointer to the left. Now since 2 < 6 stop moving the right pointer.

Swap the values at the left and right pointers and move each once more and return the value of the left pointer.

The index of the left pointer will be returned and we need to use that to divide the array and perform the Quick sort on that part.

Quick sort is performed until all elements on the left array and right array are sorted. So we call partition() and based on that we divide the array in to parts and we call quickSort recursively.

And we can test our quick sort out:

Here is a visual of a quick sort in action:

Bubble Sort

The bubble sort sorts every pair of adjacent values and the first value will swap with the second if it is greater. The idea is that the larger value “bubbles up” to the top and after each pass through the array the elements to the right are in order.

Say we have an array as follows : [6, 4, 2, 5, 7] First we compare 6 and 4. 4 is smaller than 6 so we swap the pair. We do this continually until the array is sorted.

First iteration: [6, 4, 2, 5, 7] -> [4, 6, 2 ,5, 7] -> [4, 2, 6, 5, 7] -> [4, 2, 5, 6, 7]

Second iteration: [4, 2, 5, 6, 7] -> [2, 4, 5, 6, 7]

The algorithm continues through the second iteration, seeing that the array is already sorted in each spot nothing will change.

Lastly, bubble sort needs a final pass through the array to ensure no other swaps are necessary

Above is a possible implementation of a bubble sort in JavaScript. We loop over the array, we compare an element to the element next to it, if it is greater than it, we swap the two. Rinse and repeat. Here is our test: