Sunday, 20 May 2012

Difference between Insertion and Selection Sort

Insertion Sort
Selection Sort
Insertion sort, sorts a set of records by inserting record into an existing sorted file. The closer the file is sorted the more efficient the insertion sort becomes.

A selection sort is one in which successive elements are selected in order and placed into their proper sorted positions.

In insertion sort we know the element and search for its place.

In selection sort we know the place and search the element to be placed.
It is a live sorting technique. It can sort the data as it arrives.

It requires all the data to be present at the beginning of the sort.

This is a stable sorting algorithm.
This is not a stable sorting algorithm.

If the initial data is sorted then -
Comparisons = n*(n-1)/2
Moves = 0
Comparisons = n*(n-1)/2
Moves = 0

If the initial data is in reverse order then -
Comparisons =(n-1)
Moves = 2+3+4+ ----- +n
Comparisons = n*(n-1)/2
Moves = n/2 * 3 (each swap consist of 3 moves)


No comments:

Post a Comment

Your comments are very much valuable for us. Thanks for giving your precious time.