All sorts of Sort in JavaScript

A chronicle of my collation of seven sort algorithms implemented in JavaScript

Since my earliest memories of mathematics I have been fascinated with algorithms. This was reinforced when I discovered computer programming and was able to not only exercise algorithms in code but also illustrate the more geometric algorithms in graphics. For some time now I have considered compiling a collection of the more well known sort algorithms and this article is a record of the process. This article does not compare implementations of their relative performance characteristics other than grouping them between Simple and Efficient solutions.

This article was largely prompted by a number of YouTube videos from the Computerphile channel:

Of course JavaScript has its own sort mechanism, which like many languages, employs a form of the Quick Sort algorithm described below. However, one of the best ways to understand how something works it to try and recreate it yourself.

The test harness

Each Sort is demonstrated through its own HTML test harness, all of which have the same structure as follows.

 

<!DOCTYPE html>

<html lang=”en”>

<head>

 <meta charset=”UTF-8″>

 <meta name=”viewport” content=”width=device-width, initial-scale=1.0″>

 <meta http-equiv=”X-UA-Compatible” content=”ie=edge”>

 <title>Bubble Sort</title>

 <style>

   label, textarea {

     margin-bottom: 1em;

     display: inline-block;

   }

 </style>

</head>

<body>

 <h1>SORT_TYPE</h1>

 <label for=”start”>Start:</label><input type=”text” id=”start” readonly=’readonly’>

 <br/>

 <textarea id=”results” cols=”80″ rows=”20″></textarea>

 <br/>

 <label for=”end”>End:</label><input type=”text” id=”end” readonly=’readonly’>

 

 http://SortAlgorithm.js’

 

   const arrRandData = [

     61,20,56,25,73,2,57,27,73,95,1,34,4,99,75,59,96,54,59,10,

     69,74,93,94,89,94,11,25,29,71,37,80,75,39,83,68,90,94,63,32,

     16,85,15,42,97,60,34,11,69,64,50,74,40,93,91,40,0,39,16,59,

     69,71,26,53,39,60,69,77,95,53,99,16,72,17,83,84,70,69,21,48,

     37,31,25,51,71,41,49,82,24,93,57,85,40,24,90,56,30,16,64,17,

     23,24,46,3,27,4,94,76,74,60,34,5,16,0,32,84,4,64,61,15]

   document.querySelector(‘#start’).value = Date.now()

   document.querySelector(‘#results’).value = SortAlgorithm(arrRandData).join()

   document.querySelector(‘#end’).value = Date.now()

 

</body>

</html>

The same test data is used for each algorithm, they all have the same target of ordering 120 numbers in ascending order and a date/time stamp is captured before and after execution.

Simple Sorts

What this group of Sorts lack in efficiency they gain in simplicity and therefore make for great examples of how some algorithms work. Many Sort algorithms have a “swap” operation in common, especially is the data is orders within the memory used by the source data. A swap operation usually involves three actions to exchange values A and B.

  1. Store one of the values (A) to swap in a temporary variable (T).
  2. Set the same location (A) to the value of the second value (B).
  3. Set the value of (B) to that held in the temporary variable (T).

Bubble Sort

The Bubble Sort employs a nested pair of loops. The outer traverses all values in the dataset except the last. The inner loop runs from the current outer value to the end. Each value of the inner loop compares it with its next neighbour and swaps them if out of order. This continues until the end is reached or not swaps are performed. The effect is that the highest values ‘bubble’ to the top (right.)

8, 2, 1, 7, 9, 3, 5, 6, 4        8, 2, 1, 7, 9, 3, 5, 6, 4

                |_______^|________^

2, 1, 7, 8, 3, 5, 6, 4, 9        2, 1, 7, 8, 3, 5, 6, 4, 9

                |___^    |_________^

1, 2, 7, 3, 5, 6, 4, 8, 9        1, 2, 7, 3, 5, 6, 4, 8, 9

                           |_________^

1, 2, 3, 5, 6, 4, 7, 8, 9        1, 2, 3, 5, 6, 4, 7, 8, 9

                               |___^

1, 2, 3, 5, 4, 6, 7, 8, 9        1, 2, 3, 5, 4, 6, 7, 8, 9

                           |___^

1, 2, 3, 4, 5, 6, 7, 8, 9

Insertion Sort

If there is only one element, it is already sorted so exit. Otherwise, traverse all but the first element from start to end. Within each cycle locate the location in the sorted list where the current value is to be inserted. Shuffle all following sorted elements right upto and including the current value, then insert it in the sorted group.

8, 2, 1, 7, 9, 3, 5, 6, 4        8, 2, 1, 7, 9, 3, 5, 6, 4   

^_|

2, 8, 1, 7, 9, 3, 5, 6, 4        2, 8, 1, 7, 9, 3, 5, 6, 4

^___|

1, 2, 8, 7, 9, 3, 5, 6, 4        1, 2, 8, 7, 9, 3, 5, 6, 4

      ^__|

1, 2, 7, 8, 9, 3, 5, 6, 4        1, 2, 7, 8, 9, 3, 5, 6, 4

      ^______|

1, 2, 3, 7, 8, 9, 5, 6, 4        1, 2, 3, 7, 8, 9, 5, 6, 4

          ^______|

1, 2, 3, 5, 7, 8, 9, 6, 4        1, 2, 3, 5, 7, 8, 9, 6, 4

              ^______|

1, 2, 3, 5, 6, 7, 8, 9, 4        1, 2, 3, 5, 6, 7, 8, 9, 4

          ^__________|

1, 2, 3, 4, 5, 6, 7, 8, 9

Selection Sort

Set the Index to 0 and locate the minimum value in the remainder of the list. Swap the minimum value with that at the Index and move it right 1. Repeat until the list is sorted.

8, 2, 1, 7, 9, 3, 5, 6, 4        8, 2, 1, 7, 9, 3, 5, 6, 4

^___|

1, 2, 8, 7, 9, 3, 5, 6, 4        1, 2, 8, 7, 9, 3, 5, 6, 4

   ^

1, 2, 8, 7, 9, 3, 5, 6, 4        1, 2, 8, 7, 9, 3, 5, 6, 4

       ^_____|

1, 2, 3, 7, 9, 8, 5, 6, 4        1, 2, 3, 7, 9, 8, 5, 6, 4

           ^_________|

1, 2, 3, 4, 9, 8, 5, 6, 7        1, 2, 3, 4, 9, 8, 5, 6, 7

               ^___|

1, 2, 3, 4, 5, 8, 9, 6, 7        1, 2, 3, 4, 5, 8, 9, 6, 7

                   ^___|

1, 2, 3, 4, 5, 6, 9, 8, 7        1, 2, 3, 4, 5, 6, 9, 8, 7

                       ^___|

1, 2, 3, 4, 5, 6, 7, 8, 9

Shell Sort

The Shell Sort algorithm is an enhancement of the Insertion Sort with a ‘divide and conquer preparatory step. First we calculate an interval (h) based on Knuth’s Formula (h = h * 3 + 1) such that h is the largest value less than the number of data items to be sorted. With a dataset of [8, 2, 1, 7, 9, 3, 5, 6, 4] (9 values), h = 4.

Preparation

8, 2, 1, 7, 9, 3, 5, 6, 4            8, 2, 1, 7, 9, 3, 5, 6, 4 (no change)

^_______^

8, 2, 1, 7, 9, 3, 5, 6, 4            8, 2, 1, 7, 9, 3, 5, 6, 4 (no change)

   ^_______^

8, 2, 1, 7, 9, 3, 5, 6, 4            8, 2, 1, 7, 9, 3, 5, 6, 4 (no change)

       ^_______^

8, 2, 1, 7, 9, 3, 5, 6, 4            8, 2, 1, 6, 9, 3, 5, 7, 4

           ^_______^

8, 2, 1, 7, 9, 3, 5, 6, 4            4, 2, 1, 6, 8, 3, 5, 7, 9

^_______^_______^

H is then reduced as follows h = (h – 1) /3 = 1 (last cycle.)

We then perform an Insertion Sort.

4, 2, 1, 6, 8, 3, 5, 7, 9            2, 4, 1, 6, 8, 3, 5, 7, 9

^_|

2, 4, 1, 6, 8, 3, 5, 7, 9            1, 2, 4, 6, 8, 3, 5, 7, 9

^___|

1, 2, 4, 6, 8, 3, 5, 7, 9            1, 2, 3, 4, 6, 8, 5, 7, 9

      ^______|

1, 2, 3, 4, 6, 8, 5, 7, 9            1, 2, 3, 4, 5, 6, 8, 7, 9

              ^____|

1, 2, 3, 4, 5, 6, 8, 7, 9            1, 2, 3, 4, 5, 6, 7, 8, 9

                      ^__|

Efficient Sort

The following algorithms are not necessarily the most efficient sorts, just more efficient that those described above. How best to measure efficiency is a subject in of itself and out of score of this article. If this is a topic of interest to you, investigate “Big O notation”.

Heap Sort

The first algorithm in this group overlays a form of binary tree on top of the source data array, which enabled rapid ordering of elements in the array. The top-most (root) node in the tree starting the first element (index zero) of the array, its children always having index 1 (left) and (right), and the next level referencing indexes 3 to 6. Given any index (P) of a parent, the index of the left child can be calculated as 2 x P + 1, and right calculated as 2P + 2. Calculating the index of parent given that of either child is also trivial |(C – 1) /2|, but I have not found in necessary in my implementation. I suspect I have missed a trick.

This form of binary tree (Heap) mandates that each group of Parent and (up to two) Children have to be arranged so the Parent has the higher value. Using the formulae given above we can check, from the bottom-up, this condition is in place before we start processing. This may take several passes to ensure any rearrangements are fully taken into consideration. Once organised, this only ensures the aforementioned mandate, there is no guarantee the child value are organised in ascending order. However, the root node will be the highest value in the dataset.

The next stage is repeated until the Heap is fully exhausted through the following steps. We retain a reference to an ‘insertion point’, which starts being the last item in the array. Root is exchanged with the item at the Insertion Point, which we re-reference to the preceding item in the array. We need to re-balance the Heap top-down following a path made by exchanging each parent with one of its children until not change is required or we get to the bottom of the Heap. The process repeats until all data items have been removed from the Heap.

8, 2, 1, 7, 9, 3, 5, 6, 4

         8

       /  \

      2  1

     / \    / \

    7 9  3 5

    / \

    6 4

         9

       /  \

      8   5

     / \    / \

    7 2  3 1

    / \

    6 4

    Exchange the root value at the insert point (4)

         4        List = [9]

       /  \

      8   5

     / \    / \

    7 2  3 1

    /

    6

         8        List = [9]

       /  \

      7   5

     / \    / \

    6 2  3 1

    /

    4

         4        List = [8,9]

       /  \

      7   5

     / \    / \

    6 2  3 1

         7        List = [8,9]

       /  \

      6   5

     / \    / \

    4 2  3 1

         1        List = [7,8,9]

       /  \

      6   5

     / \    /

    4 2  3

         6        List = [7,8,9]

       /  \

      4   5

     / \    /

    1 2  3

         3        List = [6,7,8,9]

       /  \

      4   5

     / \

    1 2

         5        List = [6,7,8,9]

       /  \

      4   3

     / \

    1 2

         2        List = [5,6,7,8,9]

       /  \

      4   3

     /

    1

         4        List = [5,6,7,8,9]

       /  \

     2   3

    /

    1

         1        List = [4,5,6,7,8,9]

       /  \

     2   3

         3        List = [4,5,6,7,8,9]

       /  \

     2   1

         1        List = [3,4,5,6,7,8,9]

       /

     2

         2        List = [3,4,5,6,7,8,9]

       /

     1

         1        List = [2,3,4,5,6,7,8,9]

    List = [1,2,3,4,5,6,7,8,9]

Merge Sort

This, and the next, approach to sorting employ a ‘divide and conquer’ approach by manipulating the source data array into groups using variables they store key indexes into the data structure. With Merge Sort we split the array in two, each half we again split is two, and we repeat until we have no more than 2 elements, which can then easily we rearranged in ascending order. The process then ‘merges’ the group back together, whilst retaining the ascending order, to form a single dataset.

8, 2, 1, 7, 9, 3, 5, 6, 4

8, 2, 1, 7,    |    9, 3, 5, 6, 4

8, 2,     |    1, 7,    |    9, 3,    |    5, 6,4

8, 2,     |    1, 7,    |    9, 3,    |    5, 6,    |    4

2, 8,    |    1, 7,    |    3, 9,    |    5, 6,    |    4

2, 8,    |    1, 7,    |    3, 9,    |    4, 5, 6,

1, 2, 7, 8,        |    3, 4, 5, 6, 9

1, 2,            7, 8,

|            |

1, 2,    3, 4, 5, 6,     7, 8,    9

    |            |

    3, 4, 5, 6,         9

1, 2, 3, 4, 5, 6, 7, 8, 9

 

Quick Sort

To commence a Quick Sort we have to select a Pivot. This is often the last item in the dataset, assuming a good random distribution, which we hope will be a mean value. To make sure, we can always select the first, last and middle values, select the average value and replace the last value with it, if required. We then traverse the rest of the dataset, moving all values greater than or equal to the pivot, right of the pivot. Finally we recursively repeat the process with each half in the same manner.

                (4)                4

    8, 2, 1, 7, 9, 3, 5, 6    |            2,1,3    |    8,7,9,5,6

                    4

            (3)        |        (6)

        2,1    |            5    |    8,7,9

                    4

            3        |        6

    (1)        |            5    |        (9)

    |    2                        8,7    |

                    4

            3        |        6

    1        |            5    |            9

    |    2                        (7)        |

                                |    8

    1    2    3        4    5    6    7    8    9

Further reference

https://www.toptal.com/developers/sorting-algorithms

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

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/sorting.html

Also, check out my collection of over a dozen sort algorithms implemented in JavaScript.