I recently wrote an article called Should You Learn Data Structures and Algorithms?. It is primarily about the searching and sorting algorithms which many people seem to place so much emphasis on, especially in the educational sphere. My view is that the need to implement these algorithms is rare so you would be better off concentrating on learning topics which you will need on a day to day basis. However, you might need to learn at least the basics just to convince others of your prowess so I have put together a short bit of code to illustrate a couple of the best-known sorting algorithms.

I have started of with bubble sort and selection sort. Neither are very efficient but they are simple to understand and implement. In the future I will expand this project with further algorithms.

Bubble Sort

This is a screenshot of the output of this project after a sample run of the bubble sort algorithm. It sorts in steps, the number of steps being one less than the number of items to be sorted. Each row represents one step, with the unsorted part of the data being shown in red and the sorted part in green.

The basic bubble sort algorithm is as follows.

• Iterate the list from left to right


• If the item after the current one is lower than the current one swap them


• The highest item will migrate or "bubble" up to its correct position at the end of the list


• Repeat with the unsorted part of the list

The list being sorted can be regarded as being in two parts, the sorted part on the right which gets ever larger and the unsorted part on the left which gets ever smaller.

Selection Sort

The selection sort algorithm is as follows.

• Search the entire list for the smallest item


• Swap it with the first item - it is now in its correct place


• Search the remainder of the list for its smallest item and swap it with the second item


• Repeat until you reach the last but one item in the list

As with bubble sort the list is in two parts, but this time the sorted part is on the left and the unsorted part on the right.

Swapping Integers Using Exclusive Or

Sorting algorithms need to be able to swap two values, and the most obvious way of doing this is by using a temporary variable, for example

let a = 45;
let b = 99;
let temp;

temp = a; // temp = 45
a = b; // a = 99
b = temp; // b = 45

However, if we are swapping integers we can use a trick with XOR, the symbol for which in JavaScript is ^. The following code and comments show how this works. Pay particular attention to the binary values in the comments.

let a = 45; // 00101101
let b = 99; // 01100011
a = a ^ b;  // 01001110
b = a ^ b;  // 00101101
a = a ^ b;  // 01100011

I think this is a neat and clever bit of code so I'll be using it in this project.

Coding Sorting Algorithms in JavaScript

The project consists of an HTML page, a small JavaScript file containing a function to output text to the page, a graphic, a CSS file and a JavaScript file called sortingalgorithms.js.

The files can be downloaded as a zip file from the Downloads page, or you can clone or download the Github repository.

Source Code Links

ZIP File
GitHub

The HTML file contains an empty <div> element which we will write output to, so I will just show the JavaScript listings here.

sortingalgorithms.js

window.onload = function()
{
    setEventHandlers();
}


function setEventHandlers()
{
    document.getElementById("btnBubbleSort").onclick = bubbleSort;
    document.getElementById("btnSelectionSort").onclick = selectionSort;
}


function bubbleSort()
{
    clearConsole("console");

    const data = getRandomData();
    printData(data, null, data.length);

    let last_index = data.length - 2;

    while(last_index >= 0)
    {
        for(let index = 0; index <= last_index; index++)
        {
            if(data[index] > data[index+1])
            {
                swap(data, index, index+1);
            }
        }

        printData(data, null, last_index);

        last_index--;
    }
}


function selectionSort()
{
    clearConsole("console");

    const data = getRandomData();
    printData(data, 0, null);

    let sorted_to = 0;
    let index_of_lowest = 0;
    let data_length = data.length;

    while(sorted_to < data_length - 1)
    {
        index_of_lowest = findLowestIndex(data, sorted_to);

        swap(data, sorted_to, index_of_lowest);

        sorted_to++;

        printData(data, sorted_to, null);
    }
}


function getRandomData()
{
    const size = 16;
    let data = [];

    for(let i = 0; i < size; i++)
    {
        data[i] = parseInt(Math.random() * 128);
    }

    return data;
}


function swap(data, i1, i2)
{
    if(i1 != i2)
    {
        data[i1] = data[i1] ^ data[i2];
        data[i2] = data[i1] ^ data[i2];
        data[i1] = data[i1] ^ data[i2];
    }
}


function findLowestIndex(data, start)
{
    let lowest_index = start;

    for(let i = start, l = data.length; i < l; i++)
    {
        if(data[i] < data[lowest_index])
        {
            lowest_index = i;
        }
    }

    return lowest_index;
}


function printData(data, sorted_to, sorted_from)
{
    let n;

    for(let i = 0, l = data.length; i < l; i++)
    {
        n = String(data[i]).padStart(4, " ").replace(/ /g, " ");

        if(sorted_from != null)
        {
            if(i > sorted_from)
                writeToConsole("<span class='greenbg'>" + n + "</span> ", "console");
            else
                writeToConsole("<span class='redbg'>" + n + "</span> ", "console");
        }
        else if(sorted_to != null)
        {
            if(i < sorted_to)
                writeToConsole("<span class='greenbg'>" + n + "</span> ", "console");
            else
                writeToConsole("<span class='redbg'>" + n + "</span> ", "console");
        }
    }

    writeToConsole("<br/>", "console");
}

window.onload

Here we just call another function to set event handlers.

setEventHandlers

There are two buttons on the page for the two types of sorting algorithm so we need to set their onclick event hanlers.

bubbleSort

After generating and printing a set of random data we create a last_index variable to hold the index of the end of the unsorted part of the data.

We then enter a while loop, the exit condition being when last_index hits 0. Within this loop we iterate the unsorted part of the data, swapping adjoining values where necessary. The data is then printed and last_index decremented.

selectionSort

After generating and printing our random data we need a few variables. sorted_to keeps track of the end of the sorted portion of the data, index_of_lowest is set to the index of the lowest value in the unsorted data, and data_length is used in a while loop to avoid having to repeatedly call the array's length method.

We then enter a while loop which exits when we get to the end of the data. Within this loop we call a separate function (which I'll get to in a moment) to find the lowest value in the unsorted data; this is then swapped with the first value. Finally we just need to increment sorted_to and print the data.

getRandomData

This function creates and returns an array of random data to be sorted.

swap

I described above a method for swapping integers with exclusive or, and this is implemented here.

findLowestIndex

The selection sort algorithm needs to find the lowest item in the unsorted portion of the data, and this is separated out into this function which, as well as the data itself, takes a start argument specifying the index of the beginning of the unsorted data.

printData

We need to be able to print out partially sorted data with the sorted and unsorted parts in different colours. The two algorithms I implemented for this project work in different directions so this function takes, as well as the data, arguments called sorted_to and sorted_from for data sorted from the beginning or end respectively. The colour used for each item depends on which of these arguments is set and whether each item is before or after this point.

Outro

As I mentioned earlier both these algorithms are rather inefficient and this project is intended only as a demonstration and programming exercise.

If you actually need to sort an array in production code then the built-in sort method is usually the best option in all but exceptional circumstances.

There are many more sorting algorithms and in future posts I will expand this project to implement more of them. I will also go into more detail on the efficiencies/inefficiencies of various algorithms.