Insertion Sort

Introduction

insertion sort, which is an efficient algorithm for sorting a small number of elements. Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand. To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left. At all times, the cards held in the left hand are sorted.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

pseudo code for insertion sort

INSERTION-SORT(A)
1. for j = 2 to A.length
2. key = A[ j ]
3. //Insert A[ j ] into the sorted sequence A[1, ……, j-1].
4. i= j - 1
5. while i > 0 and A[ i ] > key
6. A[ i + 1 ] = A[ i ]
7. i= i - 1
8. A[ i + 1 ] = key

Insertion Sort implementation in C

.

/* insertion sort ascending order */
#include <stdio.h>

int main ( ) {

int n , array [ 1000 ] , c , d , t ;
printf ( " Enter number of elements \n " ) ;
scanf ( " %d " , &n ) ;
printf ( " Enter %d integers \n " , n ) ;

for ( c = 0 ; c < n ; c++) {
scanf ( " %d " , &array [ c ] ) ;

}
for ( c = 1 ; c <= n - 1 ; c++ ) {
d = c ;

while ( d > 0 && array[ d ] < array[ d - 1 ] ) {
t = array[ d ] ;
array[ d ] = array[ d - 1 ] ;
array[ d - 1 ] = t ;
d - - ;
}
}
printf ( " Sorted list in ascending order: \n " ) ;

for ( c = 0 ; c <= n - 1 ; c++) {
printf ( " %d \n " , array[ c ] ) ;
}

return 0;
}

Insertion Sort implementation in C++

#include < cstdlib >
#include < iostream >

using namespace std;

//member function
void insertion_sort ( int arr[ ] , int length ) ;
void print_array ( int array[ ] , int size) ;

int main( ) {

int array[ 5 ]= { 5 , 4 , 3 , 2 , 1 } ;
insertion_sort( array , 5 ) ;
return 0 ;
}//end of main

void insertion_sort( int arr[ ] , int length ) {
int i , j , tmp ;
for ( i = 1 ; i < length ; i++ ) {
j = i ;
while ( j > 0 && arr[ j - 1] > arr [ j ]) {
tmp = arr[ j ] ;
arr[ j ] = arr[ j - 1 ] ;
arr[ j - 1 ] = tmp ;
j - - ;
}//end of while loop
print_array ( arr , 5 ) ;
}//end of for loop
}//end of insertion_sort.

void print_array ( int array[ ] , int size ) {

cout << " sorting : " ;
int j ;
for ( j = 0 ; j < size ; j ++ ) {
for ( j = 0 ; j < size ; j++ ) {
cout << " " << array [ j ] ;

}
cout << endl;

}

}//end of print_array

...................................................................
Output
insertion sort steps: 4 5 3 2 1
insertion sort steps: 3 4 5 2 1
insertion sort steps: 2 3 4 5 1
insertion sort steps: 1 2 3 4 5

Insertion Sort implementation in Java

package csehelper;

public class MyInsertionSort {
public static void main ( String[ ] args ) {
int[ ] input = { 4 , 2 , 9 , 6 , 23 , 12 , 34 , 0 , 1 } ;
insertionSort ( input ) ;
}

private static void printNumbers ( int[ ] input ) {
for ( int i = 0 ; i < input.length ; i++ ) {
System.out.print ( input [ i ] + " , " ) ;
}
System.out.println ( " \n " ) ;
}

public static void insertionSort ( int array[ ] ) {
int n = array.length ;
for ( int j = 1 ; j < n ; j++ ) {
int key = array[ j ] ;
int i = j - 1 ;
while ( ( i > - 1 ) && ( array [ i ] > key ) ) {
array [ i + 1] = array [ i ] ;
i - - ;
}
array [ i + 1 ] = key ;
printNumbers( array ) ;
}
}
}
.....................................................................
Output:
2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
0, 2, 4, 6, 9, 12, 23, 34, 1,
0, 1, 2, 4, 6, 9, 12, 23, 34,