C# Program to sort an array using Insertion Sort

Program

using System; 
namespace Application {
	public class InsertionSort {
		public InsertionSort () {
		}
		public static void Main() {
			Console.WriteLine ("Enter the size of the array"); 
			int size = Convert.ToInt32(Console.ReadLine ()); 
			int [] arr = new int[size]; 
			Console.WriteLine("Enter the array elements"); 
			for (int i = 0; i < arr.Length; i++)
				arr[i] = Convert.ToInt32(Console.ReadLine()); 
			InsertionSort sort = new InsertionSort(); 
			sort.insertionSort(arr); 
		}
		void insertionSort(int[] arr) {
			int i, j, temp; 
			for (i = 0; i < arr.Length; i++) {
				temp = arr[i]; 
				j = i - 1; 
				while ((j >= 0) && (arr[j] > temp)) {
					arr[j + 1] = arr[j]; 
					j = j - 1; 
				}
				arr[j + 1] = temp; 
			}
			Console.WriteLine("Sorted array elements:"); 
			for (i = 0; i < arr.Length; i++)
				Console.Write(arr[i] + "\t"); 
			Console.WriteLine(); 
		}
	}
}

This C# program implements Insertion Sort to sort an array entered by the user.

1. Namespace and Class Definition

• The program is inside the Application namespace.
• The InsertionSort class is defined, which contains the sorting logic.

2. Main Method (Main())

• Takes user input:

  • The program asks the user for the size of the array.
  • The user inputs the elements one by one, which are stored in an integer array.

• Creates an instance of InsertionSort and calls the insertionSort() method to sort the array.

3. Insertion Sort Logic (insertionSort(int[] arr))

• The function loops through the array elements.
• It picks an element (temp) and compares it with the previous elements.
• If the previous elements are greater, they are shifted right.
• The correct position for temp is found, and it is placed in the sorted portion.
• This process repeats for all elements until the array is fully sorted.

4. Printing the Sorted Array

• Once sorting is complete, the sorted elements are printed.

Key Points:

• Insertion Sort works by gradually building a sorted section of the array.
• It is efficient for small arrays but slower for large arrays compared to advanced sorting algorithms.
• The time complexity is O(n²) in the worst case but O(n) in the best case (already sorted array).
• It works well for nearly sorted data.

Output

$ mcs InsertionSort.cs
$ mono InsertionSort.exe
Enter the size of the array6
Enter the array elements
12
345
56
129
-98
0
Sorted array elements:
-98     0       12      56      129     345