CS Learning - Insertion Sort (Non Unique Items)

by Hari Menon

HTML

<pre>https://github.com/floydpink/computer-science-in-javascript/blob/master/algorithms/sorting/insertion-sort/insertion-sort.js
</pre>

<span>Size: </span>

<input type="text" name="size" id="size" value="90000"> <span>Max: </span>

<input type="text" name="size" id="maximum" value="100000">
<button id="generateAndSort">Generate &amp; Sort</button>
<br><pre id="output"></pre>

JavaScript

'use strict';

function setOutput(output) {
    document.querySelector('#output').innerHTML = output;
}

function generateLargeArray(size, max) {
    var array = [];
    while (array.length < size) {
        var randomNumber = Math.ceil(Math.random() * max);
        array.push(randomNumber);
    }
    return array;
}

function getCurrentTime() {
    return '\n' + new Date().toISOString() + '\n';
}

/**
 * An insertion sort implementation in JavaScript. The array
 * is sorted in-place.
 * @param {Array} items An array of items to sort.
 * @return {Array} The sorted array.
 */
function insertionSort(items) {

    var len = items.length, // number of items in the array
        value, // the value currently being compared
        i, // index into unsorted section
        j; // index into sorted section

    for (i = 0; i < len; i++) {

        // store the current value because it may shift later
        value = items[i];

        /*
         * Whenever the value in the sorted section is greater than the value
         * in the unsorted section, shift all items in the sorted section over
         * by one. This creates space in which to insert the value.
         */
        for (j = i - 1; j > -1 && items[j] > value; j--) {
            items[j + 1] = items[j];
        }

        items[j + 1] = value;
    }

    return items;
}

function sortArray(array) {
    return insertionSort(array);
}

document.querySelector('#generateAndSort').onclick = function () {
    var size = document.querySelector('#size').value;
    var max = document.querySelector('#maximum').value;
    var output = getCurrentTime();
    var array = generateLargeArray(size, max);

    console.log('Unsorted Array:');
    console.log(array);

    output += '\nUnsorted Array: Check console... \n'

    output += getCurrentTime();

    var sortedArray = sortArray(array);

    output += '\nSorted Array: Check console... \n'

    output += getCurrentTime();

    console.log('Sorted Array:');
   ...