Insertion Sort in C Programming

Insertion Sort has better average-case time complexity (O(n)) compared to Bubble Sort but can be slower than Bubble Sort in the worst case (O(n^2)). It has the advantage of being in-place sorting, meaning it doesn't require additional memory for temporary storage.

#include <stdio.h>

void insertion_sort(int arr[], int n) {
  // Iterate through each element starting from the second
  for (int i = 1; i < n; i++) {
    // Insert the current element at its correct position
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

int main() {
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("Unsorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  insertion_sort(arr, n);

  printf("Sorted array: ");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}

Explanation:

1. The insertion_sort function takes an array and its size as arguments.

2. It iterates through the array starting from the second element (i = 1).

3. For each element (key), it compares it with its preceding elements (j) while they are greater than the key.

4. If a preceding element is greater, it is shifted one position to the right, creating a space for the key.

5. This process continues until the key finds its correct position where it is smaller than all preceding elements.

6. The main function demonstrates how to use the insertion_sort function with an example array.

---

Demonstration of Sorting

Initial array:

64, 34, 25, 12, 22, 11, 90

Step 1:

• Consider the second element (34). It is already smaller than the first element (64), so its position remains the same.

Step 2:

• Consider the third element (25). It needs to be inserted before 34. Shift 34 to the right, and place 25 at the second position.

64, 25, 34, 12, 22, 11, 90

Step 3:

• Consider the fourth element (12). It needs to be inserted before 25, 34, and 64. Shift 25, 34, and 64 one position to the right each, and place 12 at the fourth position.

64, 34, 25, 12, 22, 11, 90

Step 4:

• Consider the fifth element (22). It needs to be inserted before 34. Shift 34 one position to the right, and place 22 at the fifth position.

64, 34, 25, 12, 22, 11, 90

Step 5:

• Consider the sixth element (11). It needs to be inserted before 22, 25, 34, and 64. Shift 22, 25, 34, and 64 one position to the right each, and place 11 at the sixth position.

64, 34, 25, 12, 22, 11, 90

Step 6:

• Consider the last element (90). It is already larger than all preceding elements, so its position remains the same.

Final sorted array:

11, 12, 22, 25, 34, 64, 90

This visualization demonstrates how Insertion Sort works by gradually inserting each element into its correct position within the sorted sub-array at the beginning. By visually shifting elements and updating their positions, you can understand the sorting process step-by-step.

Remember that this is just an example, and the specific steps will vary depending on the initial order of the elements in the array. However, the basic principle of inserting elements into their correct positions remains the same.