Sorting Algorithms

29 November 2019 - 142 views
I don't often start an article asking a question, but I'll make an exception today. Can you take the following array [8,3,1,9,6,5,7,2,4] and sort it in ascending order? Fairly easy right? Many programming languages provide sorting functions that make tasks such as this a one liner.

Listing 1

console.log([8,3,1,9,6,5,7,2,4].sort());

Sometimes it's easy to overlook the implementation details of such a function until you're asked to write your own, which brings me to my next question. Can you sort an array in ascending order without using builtin sort functions?

In this article I'll cover three of the simplest sorting algorithms and how to implement them in JavaScript.

Bubble Sort


The Bubble Sort algorithm is the simplest to understand and implement. The algorithm works by iterating through a collection and comparing adjacent elements. If the first element is greater than the second element then the two elements are swapped. The next iteration compares the second element with the third element and so on until the iteration is complete. The example below will help demonstrate this better. Consider the following array.

8, 3, 1, 9


Compare the first element with the second element. 8 is greater than 3. Swap elements.

3, 8, 1, 9


Compare the second element with the third element. 8 is greater than 1. Swap elements.

3, 1, 8, 9


Compare the third element with the fourth element. 8 is less than 9. Do not swap elements.

3, 1, 8, 9


The final result after the first iteration is 3, 1, 8, 9. As you can see, the array is still not sorted. This means another iteration cycle is required until the array if finally sorted. Depending on the size of the array and how the elements are positioned, the Bubble Sort algorithm can take many iteration cycles to sort an array. The following code sample below demonstrates a simple Bubble Sort algorithm.

Listing 2

    function bubbleSort(array){
        let swapped = true;

        while(swapped){
            swapped = false;
            for(let i = 0; i < array.length; i++){
                let v1 = array[i];
                let v2 = array[i+1];
                
                if(v1 > v2){ 
                    array[i] = v2;
                    array[i+1] = v1;
                    swapped = true;
                }
            }
        }
        return array;
    }

Selection Sort


The Selection Sort algorithm is based on finding the minimum/maximum element in an array and moving it to the start/end position of an array depending on the sort direction. Assume that we want to sort an array in ascending order. The algorithm will first find the smallest value in the array and swap it with the element at the beginning of the array. The next iteration will find the smallest value between the second element and the end of the array. When the smallest value between this range is found, the two elements are once again swapped. This process continues until the array is finally sorted. This algorithm is considered more efficient than the Bubble Sort algorithm because it does not iterate over elements that have been sorted. This means that the search to find the smallest value becomes shorter for each iteration. Let's take a look at a simple example.

8, 9, 1, 3


First we iterate over the entire collection to find the smallest value. Once found, it is swapped with the element at the beginning of the array. In this case, 1 is the smallest value. After the first iteration, the array now looks like the following.

1, 9, 8, 3


The next iteration starts at the second element position and continues to the end of the array looking for the smallest value. Once found the two elements are swapped.

1, 3, 8, 9


Although the array is now sorted, the algorithm will continue to iterate over the remaining array elements. The following code sample below demonstrates a simple Selection Sort algorithm.

Listing 3

    function selectionSort(array){
        for(let i = 0; i < array.length; i++){

            let minimum = i;

            for(let j = (i + 1); j < array.length; j++){
                if(array[j] < array[minimum]){
                    minimum = j;
                }
            }

            let v1 = array[i];
            let v2 = array[minimum];

            array[i] = v2;
            array[minimum] = v1;
        }
        return array;
    }

Insertion Sort


The Insertion Sort algorithm sorts an array by shifting and inserting elements at the correct position. The principle is similar to how you would organize a set of cards. Assume you are given a series of random playing cards one at a time. Every time you take a card, you insert it at the correct position by scanning the cards you are holding. When a card is inserted, the positions of the surrounding cards are also affected. The following code sample below demonstrates a simple Insertion Sort algorithm.

Listing 4

    function insertionSort(array){
        for(let i = 1; i < array.length; i++){
            let j = i - 1;
            let current = array[i];

            while(>=0 && array[j] > current){
                array[j+1] = array[j];
                j--;
            }
            array[j+1] = current;
        }
        return array;
    }