Insertion Sort Algorithm in C#

1. Introduction

The Insertion Sort algorithm is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on larger lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, for small datasets, it can be faster because of its simple nature.

2. Implementation Steps

1. Start from the second element (index 1), assume the first item (index 0) is sorted.

2. Compare the current element with the previous elements.

3. If the current element is smaller than the previous element, compare it with the elements before the previous element. Repeat this process until you find an element smaller than the current element or reach the start of the array.

4. Insert the current element in the correct position so that the elements before are smaller and the elements after are larger.

5. Repeat the process for all the elements in the array.

3. Implementation in C#

using System;
public class InsertionSort {
    public static void Sort(int[] arr) {
        for (int i = 1; i < arr.Length; i++) {
            int key = arr[i];
            int j = i - 1;
            // Move elements of arr[0..i-1] that are greater than key
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }
}
public class Program {
    public static void Main() {
        int[] arr = {12, 11, 13, 5, 6};
        Console.WriteLine("Unsorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
        InsertionSort.Sort(arr);
        Console.WriteLine("\nSorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
    }
}

Output:

Unsorted array:
12 11 13 5 6
Sorted array:
5 6 11 12 13

Explanation:

1. The InsertionSort class contains a static method named Sort which sorts an integer array using the insertion sort technique.

2. Within the Sort method, we start by considering the second element of the array and compare it with the first element. If it's smaller, we swap them.

3. We then move on to the third element and compare it with the second, and then the first. We continue this process until we've iterated through the entire array, inserting each element in its correct position in the sorted section of the array.

4. The Main method showcases the sorting of an integer array using the InsertionSort class, displaying both the unsorted and sorted arrays.