Learn Computer Science programming - C# and C++ Algorithms

 
Insertion Sort


This is a simple sort. It inserts each item into its proper place in the sorted list. It requires two list structures. The first is for the source and the second for the sorted items. Like the bubble sort, the insertion sort has a complexity of O(n2). Although it has the same complexity, the insertion sort is about twice as efficient as the bubble sort. It is inefficient for large lists. 




Code
c_insertion_sort.zip
File Size: 22 kb
File Type: zip
Download File

using System;

class InsertionSort
{
    static void Main()
    {
        int[] array = new int[] {11, 15, 4, 48, 33, 2, 8};

        foreach (int x in array)
        {
            Console.Write("{0,2} ", x);
        }
        Console.WriteLine();

        for (int x = 1; x < array.Length; x++)
        {
            int v = array[x];

            // Work backwards through array
            int j = x;
            while (j > 0 && array[j-1] > v)
            {
                array[j] = array[j-1];
                j--;
            }

            array[j] = v;
        }

        foreach (int x in array)
        {
            Console.Write("{0,2} ", x);
        }
        Console.WriteLine();
        Console.Write("Press Enter...");
        Console.ReadLine();
    }
}