Insertion Sort Algorithm

Insertion sort is a to some extent an interesting algorithm with an expensive runtime characteristic having O(n2). This algorithm can be best thought of as a sorting scheme which can be compared to that of sorting a hand of playing cards, i.e., you take one card and then look at the rest with the intent of building up an ordered set of cards in your hand.

Algorithm for Insertion Sort

1. algorithm Insertion_sort(list)
2. Pre: list 6= fi
3. Post: list has been sorted into values of ascending order
4. unsorted <- 1
5. while unsorted < list.Count
6. hold <- list[unsorted]
7. i à unsorted - 1
8. while i >= 0 and hold < list[i]
9. list[i + 1] <- list[i]
10.  i <- i - 1
11. end while
12. list[i + 1] <- hold
13. unsorted <- unsorted + 1
14. end while
15. return list
16. end Insertion_sort

Example:

#include <iostream>
#include <conio.h>

int main()
{
    int a[16], i, j, k, tmp;
    cout << "enter the number of elements\n";
    for (i = 0; i < 6; i++) { cin >> a[i];
    }
    for (i = 1; i < 6; i++) { for (j = i; j >= 1; j--) {
            if (a[j] < a[j - 1]) {
                tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
            }
            else
                break;
        }
    }
    cout << "sorted array\n" << endl;
    for (k = 0; k < 6; k++) {
        cout << a[k] << "\t";
    }
}

Output: