Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by iteratively taking an element from the unsorted portion of the array and inserting it into the correct position within the sorted portion.

 
How Insertion Sort Works:

Build a Max Heap:

Arrange the elements in a binary tree structure to satisfy the max heap property, where each parent node is greater than its children.
 

Extract the Root (Maximum Element):

Remove the root element (maximum value) of the heap and swap it with the last element in the heap.
 

Re-heapify:

Restore the heap property by “heapifying” the remaining elements. This involves comparing the new root with its children and swapping if necessary, then recursively heapifying the affected subtree.
 

Repeat Extraction:

Repeat the process of extracting the root and re-heapifying until all elements are sorted.
 

End Condition:

The algorithm completes when all elements are extracted from the heap and placed in their correct positions in the array.
 

 

Time Complexity:

Best Case: O(n), when the array is already sorted.

Average Case: O(n²), when the array is unordered.

Worst Case: O(n²), when the array is in reverse order.

 
Space Complexity:

O(1), because Insertion Sort is an in-place sorting algorithm.
 

 

using System;

namespace CommonInsertion_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] numbers = new int[10] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };
            Console.WriteLine("\nOriginal Array Elements:");
            PrintIntegerArray(numbers);
            Console.WriteLine("\n\nSorted Array Elements:");
            PrintIntegerArray(InsertionSort(numbers));
            Console.WriteLine("\n");
            Console.ReadLine();
        }

        static int[] InsertionSort(int[] inputArray)
        {
            for (int i = 0; i < inputArray.Length - 1; i++) { for (int j = i + 1; j > 0; j--)
                {
                    if (inputArray[j - 1] > inputArray[j])
                    {
                        int temp = inputArray[j - 1];
                        inputArray[j - 1] = inputArray[j];
                        inputArray[j] = temp;
                    }
                }
            }
            return inputArray;
        }
        public static void PrintIntegerArray(int[] array)
        {
            foreach (int i in array)
            {
                Console.Write(i.ToString() + "  ");
            }
        }


        public static int[] InsertionSortByShift(int[] inputArray)
        {
            for (int i = 0; i < inputArray.Length - 1; i++) { int j; var insertionValue = inputArray[i]; for (j = i; j > 0; j--)
                {
                    if (inputArray[j - 1] > insertionValue)
                    {
                        inputArray[j] = inputArray[j - 1];
                    }
                }
                inputArray[j] = insertionValue;
            }
            return inputArray;
        }

    }
}