Insertion sort and its Implementation in ‘C’

Insertion sort is one of the simplest sorting algorithms, it works the way we sort the playing cards. It iterates up the given array, and growing a sorted array behind. At each array-position, it checks the value there against the value in the previous array-position. If larger, it leaves the element in that position and moves to the next. If smaller, it inserts the element into the correct position, shifting the larger values up to make space.

Example illustrating Insertion sort:

Input : 21 9 3 12 6
21 9 3 12 6 
9 21 3 12 6 // sorted subarray = {9,21}
3 9 21 12 6 // sorted subarray = {3,9,21}
3 9 12 21 6 // sorted subarray = {3,9,12,21}
3 6 9 12 21
output : 3 6 9 12 21
Insertion sort animation

Insertion sort animation. courtesy: wikipedia.org

Complexity

Time complexity : O( N --  N² -- N² ) [Best -- Average -- Worst] 
Memory          :  O(1) i.e. just the input array:"in place"
Stable          :  Yes i.e. doesn't change relative order of elements with same key
# N being the number of elements in the array

You can read about complexities of other sorting algorithms here.

Usage

It is much less efficient on larger arrays than the advanced sorting algorithms like quicksort, merge sort and heapsort. Easier to implement, more efficient in practice that the other O(N²) algorithms like selection sort and bubble sort.

Bottom line: Use this over selection or bubble sort.

Implementation in C

Question: Sort an array of integers in increasing order using insertion sort algorithm (format similar to most of the online programming contests )

Input:

First line of input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.

Output: Sorted array

Sample Input

3
5 4 7 9 3 1
3 4 5 5
4 6 10 6 7

Sample Output

1 3 4 7 9
4 5 5 
6 6 7 10

Code

Brief explanation is given in the gist.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s