Sorting Algorithms

How to Master Sorting Algorithms in JavaScript with Examples

Sorting is an important part of any software program. It enables users to organize and reorganize items in an order of their choice. Hence, making it easier to find and retrieve an item from an entire dataset.

Every programming language has different implementations of sorting algorithms. An Algorithm is just a fancy word to mean a set of instructions for what a program should do.

In this article, we discuss the various sorting algorithms in JavaScript. They include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Bucket Sort, Counting Sort, and Radix sort.

We have included examples which you can run and experiment with straight from your terminal if you have Node.js installed.

Bubble Sort

Bubble sort works by stepping through the list to be sorted and comparing an item to the one next to it and swaps them if they are in the wrong order.

It bubbles through a list of items as it pushes smaller items to the top of the list, hence the name bubble sort. This process is done repeatedly until the list is in order.

Bubble sort is the simplest algorithm to implement, however, it faces time complexities. Because of the way it works, it is slow and hence not applicable to most problems – unless the input list is almost in a sorted order.

It has a worst-case complexity of O(n2) where n is the number of items to be sorted, which is really slow.

Here is an example implementation of bubble sort;

function swap(arr, first_Index, second_Index){ 
  var temp1 = arr[first_Index]; 
  arr[first_Index] = arr[second_Index]; 
  arr[second_Index] = temp1; 
} 

function bubble_sort(array_list){ 
  var len = array_list.length, i, j, end; 
  for (i=0; i < len; i++){ 
    for (j=0, end=len-i; j < end; j++){ 
      if (array_list[j] > array_list[j+1]){ 
        swap(array_list, j, j+1); 
      } 
    } 
 } 
return array_list; 
}

console.log(bubble_sort([3, 0, 2, 5, -1, 4, 1, 400, 3993739, 32, 2, -45, 647, 84, 90, 484]));

Insertion Sort

Insertion Sort works the way you can sort playing cards in your hand. By shifting elements one by one and inserting the right element at the right position, it builds the final sorted list one item at a time.

It has similarities to bubble sort in that it is simple to implement, and has a worst-case complexity of O(n2). Despite being easy to implement, it’s actually really slow and hardly used for most problems. It is more efficient than Bubble Sort.

It is appropriate for small data sets or when adding items to an already sorted dataset. Insertion Sort is adaptive in that, it can sort items as you continue adding more items to the array. It only requires a constant amount of additional space to run, i.e. O(1).

Here is an example implementation of insertion sort;

function insertion_sort(array) { 
  var length = array.length; 

    for(var i = 1, j; i < length; i++) { 
      var temp1 = array[i]; 
      for(var j = i - 1; j >= 0 && array[j] > temp1; j--) { 
        array[j+1] = array[j]; 
      } 
      array[j+1] = temp1; 
    } 
  return array; 
}

console.log(insertion_sort([3, 0, 2, 5, -1, 4, 1, 400, 3993739, 32, 2, -45, 647, 84, 90, 484]));

Selection Sort

Selection Sort divides the dataset into two parts; a sorted subarray and unsorted subarray. Initially, the sorted subarray is empty, and the unsorted subarray contains all the dataset.

It works by scanning the entire list of the unsorted subarray and picking the smallest element, then putting it at the sorted array from left to right. It repeats the process until the unsorted subarray is empty and all elements have been added to the sorted subarray.

It has a worst-case complexity of O(n2), n being the number of items in the list. Hence, it performs worse with large datasets. Additionally, it performs worse than the similar Insertion Sort. It is highly effective for small datasets in the range of 10 to 20, as compared to using Merge Sort.

Here is an example implementation of selection sort;

function swap(array, firstIndex, secondIndex) { 
  var temp1 = array[firstIndex]; 
  array[firstIndex] = array[secondIndex]; 
  array[secondIndex] = temp1; 
} 

function indexOfMinimum(array, startIndex) { 
  var minValue = array[startIndex]; 
  var minIndex = startIndex; 

  for (var i = minIndex + 1; i < array.length; i++) { 
    if (array[i] < minValue) { 
      minIndex = i; 
      minValue = array[i]; 
    } 
  } 

  return minIndex; 
} 

function selection_sort(array) { 
  var startIndex = 0; // Start at 0 
  for (var i = 0; i < array.length; i++) { 
    startIndex++; 
    var minIndex = indexOfMinimum(array, i); 
    swap(array, minIndex, i); 
  } 
  return array; 
} 

const array = [3, 0, 2, 5, -1, 4, 1, 400, 39739, 32, 2, -45, 647, 84, 90, 484, -100]; 
console.log(selection_sort(array));

Merge Sort

Merge Sort employs the divide-and-conquer algorithmic pattern in its implementation. This pattern involves dividing a problem into smaller problems, solving the smaller recursively and combining the solutions to the smaller problems to come up with a solution of the bigger problem.

It works by dividing the unsorted lists into n sub-lists, (where n is the number of items in the unsorted list). With each sub-list containing one element, the sub-lists are considered sorted. It then repeatedly merges the sub-lists to make new sorted sub-lists until only one sorted list is left.

Merge sort is an efficient and general-purpose sorting algorithm that is commonly used. It has worst-case, best-case and average-case performance of O(n log n); this makes it one of the most preferred sorting algorithms. However, it is complex to implement;

Here is an example implementation of merge sort;

function merge_sort(array) { 
  const lenngth = array.length 
  // if the length of the array == 1, then it's sorted already 
  if (lenngth == 1) { 
    return array 
  } 

  // get middle item 
  const middleIndex = Math.ceil(lenngth / 2) 

  // split current list into two: left and right list 
  var leftArray = array.slice(0, middleIndex) 
  var rightArray = array.slice(middleIndex, lenngth) 

  leftArray = merge_sort(leftArray) 
  rightArray = merge_sort(rightArray) 

  return merge(leftArray, rightArray) 
} 


//function to solve smaller problems and merge the solutions 
function merge(leftArray, rightArray) { 
  const sorted = [] 
  while (leftArray.length > 0 && rightArray.length > 0) { 
    const leftItem = leftArray[0] 
    const rightItem = rightArray[0] 
    if (leftItem > rightItem) { 
      sorted.push(rightItem) 
      rightArray.shift() 
    } else { 
      sorted.push(leftItem); 
      leftArray.shift() 
    } 
  } 

  // if there are items still on the leftArray, add them to the results 
  while (leftArray.length !== 0) { 
    sorted.push(leftArray[0]) 
    leftArray.shift() 
  } 

  // if there are items still on the rightArray, add them to the results 
  while (rightArray.length !== 0) { 
    sorted.push(rightArray[0]) 
    rightArray.shift() 
  } 

  // merge the left and right list 
  return sorted 
} 

const array = [3, 0, 2, 5, -1, 4, 1, 400, 39739, 32, 2, -45, 647, 84, 90, 484, -100]; 
console.log(merge_sort(array));

Quick Sort

Quick Sort employs a divide and conquer algorithmic pattern just like merge sort. It works by picking an element from the unsorted list as a pivot, and partitions the array around the pivot.

By taking the pivot as a central point, it puts elements smaller than or equal to the pivot to the left, and elements greater than the pivot to the right. Elements on both sides of the pivot are quick sorted, and the process repeated until all elements in the list are sorted.

The partition process is the most important in implementing quick sort algorithm.

Depending on your choice of the pivot point, you can implement quick sort in various ways. The pivot point can be the middle element, first element, last element, or random element as the pivot point. In our example, we use middle element.

Quick sort algorithm has an average case and best-case performance of O(n log n), and worst-case performance of O(n2). A random selection of the pivot element keeps the algorithm efficient even when the data is already sorted, hence making the worst-case scenario less likely to happen.

When implemented well, it can be two to three times faster than merge sort, making it one of the most used sorting algorithms.

Here is an example implementation of quick sort;

function swap(array, left, right){ 
  var temp; 
  temp1 = array[leftIndex]; 
  array[leftIndex] = array[rightIndex]; 
  array[rightIndex] = temp1; 
} 

function partition(array, left, right){ 
  var pivot = array[Math.floor(Math.random() * array.length)]; 

  leftIndex = left; 
  rightIndex = right; 

  while (leftIndex <= rightIndex){ 
    while(array[leftIndex] < pivot){ 
      leftIndex++; 
    } 
    while(array[rightIndex] > pivot){ 
      rightIndex--; 
    } 
    if (leftIndex <= rightIndex){ 
      swap(array, left, right); 
      leftIndex++; 
      rightIndex--; 
    } 
  } 
  return leftIndex; 
} 

function quick_sort(array, left, right){ 
  var leftIndex = partition(array, left, right); 

  if (left < leftIndex - 1){ 
    quick_sort(array, left, leftIndex-1); 
  } 

  if (right > leftIndex){ 
    quick_sort(array, leftIndex, right); 
  } 

  return array; 
} 

//initialization 
var array = [3, 0, 2, 5, -1, 4, 1, 400, 2, 39739, 32, -45, 647, 84, 90, 484, -100]; 
var left=0; 
var right= array.length-1; 

console.log(quick_sort(array, left, right));

Bucket Sort

Bucket Sort, also referred to as bin sort, works by partitioning elements of an array into buckets. Each bucket can take elements from the array in a range, for example, 0 – 100, 101 – 200, etc. Individual buckets can be sorted using a different algorithm such as insertion sort, quick sort, merge sort, etc., or by using bucket sort algorithm recursively.

In our example below, we have used the Insertion Sort algorithm we discussed earlier.

Bucket sort is a distribution algorithm as its basic definition involves distributing elements into buckets. It also works as a comparison algorithm.

Bucket sort is efficient if the elements are evenly distributed over the bucket ranges. The complexities of bucket sort are determined by the individual sorting algorithm you use to sort each bucket.

The drawbacks to bucket sort is it requires more space to create more buckets if you have unevenly distributed elements, additionally, some buckets may lack elements during the distribution. The space complexity is O(n + k), where k is the number of buckets, n is the number of items. In the worst case, there could be k buckets, where one of the buckets could contain n items.

Here is an example implementation of bucket sort;

function insertion_sort(array) { 
  var length = array.length; 

  for(var i = 1, j; i < length; i++) { 
    var temp1 = array[i]; 
    for(var j = i - 1; j >= 0 && array[j] > temp1; j--) { 
      array[j+1] = array[j]; 
    } 
    array[j+1] = temp1; 
  } 

  return array; 
} 


function bucket_sort(array, bucketSize) { 
  if (array.length === 0) { 
    return array; 
  } 

  // Determine minimum and maximum values 
  var i; 
  var minValue = array[0]; 
  var maxValue = array[0]; 
  for (i = 1; i < array.length; i++) { 
    if (array[i] < minValue) { 
      minValue = array[i]; 
    } else if (array[i] > maxValue) { 
      maxValue = array[i]; 
    } 
  } 

  // Initialise buckets 
  var default_bucket_size = 5; 
  bucketSize = bucketSize || default_bucket_size; 
  var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; 
  var buckets = new Array(bucketCount); 
  for (i = 0; i < buckets.length; i++) { 
    buckets[i] = []; 
  } 

  // Distribute input array values into buckets 
  for (i = 0; i < array.length; i++) { 
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]); 
  } 

  // Sort buckets and place back into input array 
  array.length = 0; 
  for (i = 0; i < buckets.length; i++) { 
    insertion_sort(buckets[i]); 
    for (var j = 0; j < buckets[i].length; j++) { 
      array.push(buckets[i][j]); 
    } 
  } 

  return array; 
} 

//initialization 
var array = [3, 0, 2, 5, -1, 4, 1, 400, 2, 39739, 32, -45, 647, 84, 90, 484, -100]; 
var bucketSize=4; //you can set any value depending on the distribution of elements in your array 

console.log(bucket_sort(array, bucketSize));

Counting Sort

Counting Sort algorithm sorts items based on index keys between a specific range. It employs the integer sorting algorithm by counting the number of objects with distinct key values and doing calculations on those counts to determine the key value positions for the output sequence.

It’s often used with Radix Sort algorithm. Counting sort and bucket sort have a similar time analysis. However, while bucket sort requires more memory pre-allocated to hold the items of each bucket, counting sort only holds a single number count of items per bucket, hence less space.

Worst-case performance and space complexity is O(n + k)

Here is an example implementation of counting sort;

function counting_sort(array, min, max) { 
  var i 
  var z = 0 
  const count = [] 

  for (i = min; i <= max; i++) { 
    count[i] = 0 
  } 

  for (i=0; i < array.length; i++) { 
    count[array[i]]++ 
  } 

  for (i = min; i <= max; i++) { 
    while (count[i]-- > 0) { 
      array[z++] = i 
    } 
  } 
  return array 
} 

//initialization 
var array = [3, 0, 2, 5, -1, 4, 1, 400, 2, 39739, 32, -45, 647, 84, 90, 484, -100]; 
const min = Math.min(...array) //using the ES2015 new spread operator. 
const max = Math.max(...array) //using the ES2015 new spread operator 

console.log(counting_sort(array, min, max));

Radix Sort

Radix sort works by sorting data with integer keys. It groups keys by the individual digits which share similar significant position and value. Radix algorithm not only sorts integers but also strings of characters such as addresses, names, etc. Radix sort employs a non-comparison algorithm.

Like bucket sort, it distributes numbers into buckets based on number significance, i.e. numbers with 2 digits go into one bucket, numbers with 3 digits go into another bucket, etc. The distribution can be in 1s, 10s, 100s, 1000s, 10000s, etc.

Here is an example implementation of Radix sort;

function count_sort_by_digit(list, rad, exp, minValue) { 
  var i; 
  var bucketIndex; 
  var buckets = new Array(rad); 
  var output = new Array(list.length); 

  // Initialize bucket 
  for (i = 0; i < rad; i++) { 
    buckets[i] = 0; 
  } 

  // Count frequencies 
  for (i = 0; i < list.length; i++) { 
    bucketIndex = Math.floor(((list[i] - minValue) / exp) % rad); 
    buckets[bucketIndex]++; 
  } 

  // Compute cumulates 
  for (i = 1; i < rad; i++) { 
    buckets[i] += buckets[i - 1]; 
  } 

  // Move records 
  for (i = list.length - 1; i >= 0; i--) { 
    bucketIndex = Math.floor(((list[i] - minValue) / exp) % rad); 
    output[--buckets[bucketIndex]] = list[i]; 
  } 

  // Copy back 
  for (i = 0; i < list.length; i++) { 
    list[i] = output[i]; 
  } 

  return list; 
} 

//radix sort algorithm 
function radix_sort(list, rad) { 
  if (list.length === 0) { 
    return list; //exit function if arrayList empty 
  } 

  rad = rad || 10; 
  // Get minimum and maximum values 
  var minValue = list[0]; 
  var maxValue = list[0]; 
  for (var i = 1; i < list.length; i++) { 
    if (list[i] < minValue) { 
      minValue = list[i]; 
    } else if (list[i] > maxValue) { 
      maxValue = list[i]; 
    } 
  } 
  // Perform counting sort on each digit, starting from the least significant digit 
  var exp = 1; 
  while ((maxValue - minValue) / exp >= 1) { 
    list = count_sort_by_digit(list, rad, exp, minValue); 
    exp *= rad; 
  } 
  return list; 
} 

//initialization 
var arrayList = [3, 0, 2, 5, -1, 4, 1, 400, 2, 39739, 32, -45, 647, 84, 90, 484, -100]; 
var radix = 5; 

console.log(radix_sort(arrayList, radix));

Final Thoughts

In this article, we have only looked at 9 major sorting algorithms in JavaScript. These are not the only sorting algorithms as there are more including Heap sort, Shell sort, Pigeonhole sort, Cocktail sort, Spaghetti sort, Patience sort, Comb sort, Tim sort, Block sort, Library sort, Introspective sort, Tournament sort, Gnome sort, Strand sort, and Smooth sort.

Mastering sorting algorithms requires a good understanding of Computer Science Data Structures. Here are links to some resources we hope they will get you started. Happy coding!

https://www.geeksforgeeks.org/data-structures/

https://www.tutorialspoint.com/data_structures_algorithms/

https://www.coursera.org/specializations/data-structures-algorithms

https://codeburst.io/i-learned-all-data-structures-in-a-week-this-is-what-it-did-to-my-brain-547194ed5047

https://medium.com/@codingfreak/top-algorithms-data-structures-concepts-every-computer-science-student-should-know-e0549c67b4ac

From Amazon: Introduction to Algorithms, 3rd Edition (The MIT Press) 3rd Edition

From Amazon: Data Structures and Algorithms Made Easy: Data Structures and Algorithmic Puzzles

Similar Posts