Insertion-sorting a vector

The next algorithm I wanted to look at is insertion sort. The idea behind insertion sort is also pretty simple. Think about sorting a hand of playing cards you are dealt with - you scan the cards and if you find a smaller card laying to the right side of a bigger card, you pull the smaller card out and insert it to the left of the bigger card, that's it!

We split the sorting task into two functions: shift() and insertionSort(). With shift(), we move an element from the right side of a reference element (if reference element is larger) to a position before the reference element. Then in insertionSort() function, we loop from second through the last element, and shift the element to left at the appropriate position if needed using the shift() function.

Pseudocode

function shift(v, i, j)
    if (i <= j)     // do nothing
        return v
    tmp = v[i]
    while (i > j)
        v[i] = v[i - 1] 
        i = i - 1
    v[j] = tmp
    return v

function insertionSort(v)
    for 0 < i <= LENGTH(v)
        insertNeeded = false
        j = i - 1
        while (v[i] < v[j] && j >= 0)
            insertNeeded = true
            j = j - 1
        if insertNeeded == true
            shift(v, i, j + 1)
    return v

JavaScript Implementation

// insertionSort.js an algorithm to sort an array using insertion sort

function shift(v, i, j)
// inserts the ith element of array v, into jth position
// and shift everything else to the right
{
    if (i <= j)
        return v;
    var tmp = v[i];
    while (i > j)
    {
        v[i] = v[i - 1];
        i -= 1;
    }
    v[j] = tmp;
    return v;
}

function insertionSort(v)
// sorts the vector v in ascending order
// uses shift function 
{
    for (var i = 0; i <= v.length; i++) 
    // compare 2nd through last elements with every element to its left
    {
        var insertNeeded = false;
        var j = i - 1;
        while (v[i] < v[j] && j >= 0)
        {
            insertNeeded = true;
            j -= 1;
        }
        if (insertNeeded)
            shift(v, i, j + 1);
    }
    return v;
}

Let's test it

// testing 

function genRandomArray(n)
// returns an array of n random numbers
{
    var arr = [];
    for (var i = 0; i < n; i++)
    {
        arr[i] = Math.round(100 * Math.random());
    }
    return arr;
}

a = genRandomArray(10);
console.log(a);
console.log(insertionSort(a));
[
  67, 88, 13, 89, 23,
  76, 37, 45,  9, 70
]
[
   9, 13, 23, 37, 45,
  67, 70, 76, 88, 89
]