# Insertion Sort in C

0 217

**Insertion Sort,** a straightforward and **effective sorting technique**, progressively** constructs** the sorted array by individually placing each element in its proper position.

Here's a detailed overview of the **algorithm**, its time **complexity**, **space complexity**, and an **Example **implementing it:

**Algorithm:
**

Start with the **second element (index 1)** and compare it with the elements to its left.

Insert the element into its **correct position **among the already** sorted elements** to its left.

Repeat** steps 1 **and** 2** for the remaining elements, gradually expanding the sorted portion of the array.

**Time Complexity:
**

In its** best-case scenario**, Insertion Sort exhibits linear time **complexity of O(n) **when the array is pre-sorted.

**Average Case:** **O(n^2) - **When the array is randomly ordered.

**Worst Case: O(n^2) -** When the array is sorted in reverse order.

**Space Complexity:
**

**Insertion Sort** optimally organizes arrays in place, eliminating the need for supplementary memory, as it operates exclusively within the confines of the original array.

**Example:
**

// Program for Insertion sort in C #include<stdio.h>void insertionSort(int arr[], int k) { int s, key, w; for (s = 1; s < k; s++) { key = arr[s]; w = s - 1; while (w >= 0 && arr[w] > key) { arr[w + 1] = arr[w]; w = w - 1; } arr[w + 1] = key; } } void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: \n"); printArray(arr, n); insertionSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; }

**Output:
**

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

Share:

## Comments

Waiting for your comments