Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Insertion sort

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

**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.

Sort: 34 |
8 |
64 |
51 |
32 |
21 |

• 34 |
8 |
64 |
51 |
32 |
21 |

– 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^{2}).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.