Chapter: Programming and Data Structures - Sorting And Searching

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

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 (n2).

 

 

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


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