C Program insertion sort in an array
Problem:
Write a C program of insertion sort which sorts a list of elements using insertion sort algorithm.
What is insertion sort:
To know some basic about insertion sort go to Wiki and find that-
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
- Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[2]:116
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
- Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort.[3]
What is the algorithm of insertion sort:
Algorithm/Pseodocode of insert sort:
i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while
Or just in simple algorithm of insertion sort is:
// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]
See a live example of an insertion sort:
Simple C code implementation of insertion sort
To see the exact output
To see the output of your code via this site, just give proper inputs as in the below picture and click on the execute button and hopefully get the output of that program:
Tags:
Insertion sort in an array – C code implementation, insertion sort c program, c code of insertion sort in c language, insertion sort of an array, algorithm of insertion sort, insertion sort in c, c code of insertion sort, insertion sort code