27 Aug Insertion Sort in C
Let us see how to implement Insertion Sort in C Language.
What is Insertion Sort?
The insertion sort is a sorting method that contains two sub arrays, one sorted and one unsorted. The first element from the unsorted sub array is put into its correct position in the sorted sub array in each pass. At the start of the sorting, the first element of the array is considered the sorted array and the rest of the elements form the unsorted array.
Given example explains the steps required in Selection Sort.
The array before sorting starts is:
|
1 2 3 |
9 3 5 1 2 |
In the above array the first element i.e. 9 is sorted sub array and the rest of the array is unsorted sub array. 3 is added to its correct position in the sorted sub array. The array obtained is:
|
1 2 3 |
3 9 5 1 2 |
Now, 3 and 9 form the sorted sub array. 5 is added to its correct position in the sorted sub array. The array obtained is:
|
1 2 3 |
3 5 9 1 2 |
3, 5 and 9 form the sorted sub array. 1 is added to its correct position in the sorted sub array. The array obtained is:
|
1 2 3 |
1 3 5 9 2 |
1, 3, 5 and 9 form the sorted sub array. 2 is the only remaining element in the unsorted sub array. It is added to its correct position in the sorted sub array. The final sorted array obtained is:
|
1 2 3 |
1 2 3 5 9 |
Source Code
The source code for Selection Sort is as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include < stdio.h > void insertionSort(int arr[], int n) { int i, val, j; for (i = 1; i < n; i++) { val = arr[i]; j = i - 1; while ((j >= 0) && (arr[j] > val)) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = val; } } int main() { int arr[] = { 9, 3, 5, 1, 2 }; int n = 5; int i; printf("Given array is: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); insertionSort(arr, n); printf("\nSorted array is: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } |
Output
The output obtained for the above code is:
No Comments