Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

Let’s say we have an array a, so at each i-th pass, a[i] is successively compared with a[i-1], a[i-2], etc. until an element smaller than a[i] is found or the beginning of the array is reached. Elements that are found to be greater than a[i], are moved right by one position each to make room for a[i].

The time complexity of this algorithm is **O(n^2)**.

The complete source code is given below

/* * File: StraightInsertionSort.c */ #include <stdio.h> #include <stdlib.h> void straightInsertionSort(int a[], int n) { int i = 1, j, k = 0; int temp; while (i < n) { j = i - 1; temp = a[j + 1]; k = i; while (j >= 0) { if (temp < a[j]) { k = j; j--; } else { break; } } j = i; while (j > k) { a[j] = a[j - 1]; j--; } a[j] = temp; i++; } printf("\n"); printf("\nThe sorted array elements are given below\n"); for (i = 0; i < n; i++) { printf("a[%d]=%d ", i, a[i]); } } int main() { int i, n = 6; int a[] = {15, 8, 17, 12, 38, 19}; printf("\n:: Straight Insertion Sort ::\n"); printf("\nInput array elements\n"); for (i = 0; i < n; i++) { printf("a[%d]=%d ", i, a[i]); } straightInsertionSort(a, n); }

**Output**

:: Straight Insertion Sort :: Input array elements a[0]=15 a[1]=8 a[2]=17 a[3]=12 a[4]=38 a[5]=19 The sorted array elements are given below a[0]=8 a[1]=12 a[2]=15 a[3]=17 a[4]=19 a[5]=38

## No comments:

## Post a Comment