Insertion sort

INSERTION SORT:

Definition:

An insertion sort is one that sorts a set of records by inserting records into an existing sorted file.

•      Based on the technique used by card players to arrange a hand of cards

– Player keeps the cards that have been picked up so far in sorted order

– When the player picks up a new card, he makes room for the new card and then inserts it in its proper place

Algorithm:

#include <stdio.h>

#include<conio.h>

void main()

{

int n, array[1000], i, j, t;

printf("Enter number of elements\n"); scanf("%d", &n);

printf("Enter %d integers\n", n);

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

}

for (j = 1 ; j < n; j++)

{

k=j ;

while ( k> 0 && array[k] < array[k-1])

{

t = array[k]; array[k] = array[k-1]; array[k-1] = t;

k--;

}

}

printf("Sorted list in ascending order:\n");

for (i= 0; i< n; i++) { printf("%d\n", array[i]);

}

getch();

}

Execution with example:

Initially x[0] may be thought of as a sorted file, after each repetition elements from x[0] to x[k] are ordered. By moving all elements greater than y to the right direction we can insert y in the correct position.

– The algorithm sees that 8 is smaller than 34 so it swaps.

• 8  34  64  51  32  21

– 51 is smaller than 64, so they swap.

•      8  34  51  64  32  21

– The algorithm sees 32 as another smaller number and moves it to its appropriate location between 8 and 34.

• 8  32  34  51  64  21

– The algorithm sees 21 as another smaller number and moves into between 8 and 32.

•      Final sorted numbers:

•      8  21  32  34  51  64

Efficiency Analysis:

The algorithm needs n pass through for n elements with n comparisons each time so the efficiency of the algorithm is O (n²).