What is Insertion Sort?
Insertion Sort is basically the insertion of an element from a random set of numbers, to its correct position where it should actually be, by shifting the other elements if required.
Problem Description
Create a C program to perform an insertion sort and further analyze its efficiency.
Expected Input and Output
For insertion sort algorithm, we can have the following 3 different sets of input and output.
1. Average case (Unsorted array): When the input array has random distribution of numbers.
For example:
If the input array is {3, 7, 2, 9, 5}
the expected output array will have data as {2, 3, 5, 7, 9}
2. Best case (Sorted Array): When the input array is already sorted, in that case we have to make minimum number of swaps.
If the input array has data as {-3, 31, 66}
then the expected output array will have data as {-3, 31, 66}
3. Worst Case (Reverse sorted array): When the array is sorted in a reverse manner, in that case we have to make maximum number of swaps.
For example:
Participate in C Programming Certification Contest of the Month Now!
If the input array has elements as {9, 8, 6, 3, 1}
then the output array will have data as {1, 3, 6, 8, 9}