Sorting Algorithms 3 / 5: Insertion Sort

Hello again!

This is the 3rd of 5 sorting algorithms that I will be implementing and posting about.

Today I have a reverse insertion sorter for you.

An (reverse) insertion sort takes number one from the end of the array, and shuffles it along to the right until it is in the right place. Then it picks the next number along and does the same, until the whole array is sorted.

/// <summary>
/// Performs an insertion sort in the array.
/// </summary>
/// <param name="array">A reference to the array to sort.</param>
static void insertion_sort(ref int[] array)
{
for (int i = array.Length - 2; i >= 0; i--)
{
int shp = i;
//                                                      |
//make sure that we don't fall off the end of the array V
while(shp < array.Length - 1 && array[shp] > array[shp + 1])
{
swap_places(ref array, shp, shp + 1);
shp++;
}

Console.Write("i: {0} ", i);
print_array(ref array);
}
}

Here is some example output:

[ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 23 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 22 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 21 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 20 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 19 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 18 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 53, 1, 38, 47, 63, 68, 91, 93 ]
i: 17 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 14, 1, 38, 47, 53, 63, 68, 91, 93 ]
i: 16 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 67, 1, 14, 38, 47, 53, 63, 68, 91, 93 ]
i: 15 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 97, 1, 14, 38, 47, 53, 63, 67, 68, 91, 93 ]
i: 14 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 69, 1, 14, 38, 47, 53, 63, 67, 68, 91, 93, 97 ]
i: 13 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 96, 1, 14, 38, 47, 53, 63, 67, 68, 69, 91, 93, 97 ]
i: 12 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 92, 1, 14, 38, 47, 53, 63, 67, 68, 69, 91, 93, 96, 97 ]
i: 11 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 95, 1, 14, 38, 47, 53, 63, 67, 68, 69, 91, 92, 93, 96, 97 ]
i: 10 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 41, 1, 14, 38, 47, 53, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 9 [ 17, 10, 83, 67, 8, 50, 46, 63, 2, 1, 14, 38, 41, 47, 53, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 8 [ 17, 10, 83, 67, 8, 50, 46, 63, 1, 2, 14, 38, 41, 47, 53, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 7 [ 17, 10, 83, 67, 8, 50, 46, 1, 2, 14, 38, 41, 47, 53, 63, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 6 [ 17, 10, 83, 67, 8, 50, 1, 2, 14, 38, 41, 46, 47, 53, 63, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 5 [ 17, 10, 83, 67, 8, 1, 2, 14, 38, 41, 46, 47, 50, 53, 63, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 4 [ 17, 10, 83, 67, 1, 2, 8, 14, 38, 41, 46, 47, 50, 53, 63, 63, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 3 [ 17, 10, 83, 1, 2, 8, 14, 38, 41, 46, 47, 50, 53, 63, 63, 67, 67, 68, 69, 91, 92, 93, 95, 96, 97 ]
i: 2 [ 17, 10, 1, 2, 8, 14, 38, 41, 46, 47, 50, 53, 63, 63, 67, 67, 68, 69, 83, 91, 92, 93, 95, 96, 97 ]
i: 1 [ 17, 1, 2, 8, 10, 14, 38, 41, 46, 47, 50, 53, 63, 63, 67, 67, 68, 69, 83, 91, 92, 93, 95, 96, 97 ]
i: 0 [ 1, 2, 8, 10, 14, 17, 38, 41, 46, 47, 50, 53, 63, 63, 67, 67, 68, 69, 83, 91, 92, 93, 95, 96, 97 ]

Full source code (pastebin)

Binary (MD5: 01b2d774c70ce46d8e0641da948bc25e, SHA1: 537ee665162887f629200d8839b108a3e4098d38)

Tag Cloud

3d 3d printing account algorithms android announcement architecture archives arduino artificial intelligence artix assembly async audio automation backups bash batch blog bookmarklet booting bug hunting c sharp c++ challenge chrome os cluster code codepen coding conundrums coding conundrums evolved command line compilers compiling compression containerisation css dailyprogrammer data analysis debugging demystification distributed computing documentation downtime electronics email embedded systems encryption es6 features ethics event experiment external first impressions future game github github gist gitlab graphics hardware hardware meetup holiday holidays html html5 html5 canvas infrastructure interfaces internet interoperability io.js jabber jam javascript js bin labs learning library linux lora low level lua maintenance manjaro network networking nibriboard node.js operating systems own your code pepperminty wiki performance phd photos php pixelbot portable privacy problem solving programming problems projects prolog protocol protocols pseudo 3d python reddit redis reference releases rendering resource review rust searching secrets security series list server software sorting source code control statistics storage svg talks technical terminal textures thoughts three thing game three.js tool tutorial twitter ubuntu university update updates upgrade version control virtual reality virtualisation visual web website windows windows 10 xmpp xslt

Art by Mythdael