Arrays and Sorting: Insertion Sort ( with C Program source code, a tutorial and an MCQ Quiz on Sorting)

Computer Science‎ > ‎

Arrays and Sorting: Insertion Sort ( with C Program source code, a tutorial and an MCQ Quiz on Sorting)

Basic Sorting and Searching Algorithms for Arrays, at a glance

Insertion Sort

Quick Sort

Binary Search Algorithm

To go through the C program / source-code, scroll down to the end of this page

Insertion sort

Insertion sort uses linear search to find the location of the 1st element in the unsorted list, in the sorted portion of the list. It is an elementary sorting algorithm best used to sort small data sets or insert a new element in the sorted list.

Algorithm:

Insertion sort starts with a sorted list of size 1 and inserts elements one at a time. It continues inserting each successive element into the sorted list so far.

1. Suppose if the array is sorted till index i then we can sort the array till i+1 by inserting the (i+1)th element in the correct position from 0 to i+1.

2. The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.

3. As any array is sorted till 0th position (Single element is always sorted) and we know how to expand, we can sort the whole array.

To check out a Java Applet Visualization of Insertion Sort, click on the image below :

Properties:

1. Best case performance – When the array is already sorted O(n). Total number of comparisons: N – 1 and total number of exchanges: N – 1.

2. Worst case performance – When the array is sorted in reverse order O(n2). N-1 iterations of comparison and exchanges.

3. Average case performance – O(n2)

4. It is sensitive to the input as the number of comparison and exchanges depends on the input.

5. It does not require any extra space for sorting, hence O(1) extra space.

Tutorial :

Insertion Sort - C Program Source Code

#include<stdio.h>
/* Logic : Suppose if the array is sorted till index i then we can sort the arry till i+1 by inserting 
           i+1 th element in the correct position from 0 to i+1. The position at which (i+1)th element has 
           to be inserted has to be found by iterating from 0 to i. As any array is sorted till 0th postion 
           (Single element is always sorted) and we know how to expand, we can sort the whole array
 */ 
void InsertionSort(int *array , int number_of_elements)
{
        int iter,jter;
        for(iter=1;iter<number_of_elements;iter++)
        {
                int current_element = array[iter];
                jter = iter-1;
                while(jter>=0 && array[jter] > current_element)
                {
                        array[jter+1] = array[jter];
                        jter--;
                }
                array[jter+1] = current_element;
        }
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        InsertionSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

MCQ Quiz: The Basics of Sorting Algorithms- Quadratic Sorts: Check how much you know about Quadratic Time Sorting Algorithms
Your score will be e-mailed to the address filled up by you.

MCQ Quiz #1: Quadratic Time Sorting Algorithms
Google Spreadsheet Form

Related Tutorials :

Bubble Sort

One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort

Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort.

Selection Sort

Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort.

Shell Sort

An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort

An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort

In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort

Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure.

Binary Search Algorithm

Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time.

Testing Zone For Programmers-

Try out our online Multiple-Choice-Question tests in Programming and Computer Science!

Photo-credits: www.istockphoto.com

Quizzes on Basic Object Oriented Programming with C++

Quizzes on Java Programming

Quizzes on C Programming- Arrays, Strings and Pointers

Quizzes on Data Structures, Algorithms and Complexity

Tutorials on Sorting- at a glance

Bubble Sort - One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort - Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort.

Selection Sort - Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort.

Shell Sort- An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort- Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure.

Binary Search Algorithm- Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time.

insertion.png

(33k)

Prashant Bhattacharji,

Oct 7, 2012, 9:49 AM

v.4

The Learning Point

Navigation

Navigation