Explain insertion sort, Data Structure & Algorithms

Q. Explain the insertion sort with a proper algorithm. What is the complication of insertion sort in the worst case?                                                                                                                              

Ans:

 

Insertion  Sort technique: One  of  the  easiest sorting algorithms is  the  insertion  sort.

Insertion sort comprises of - 1 passes. For pass = 2 through n, insertion sort assures that the elements in the positions 1 through are in sorted order. Insertion sort makes use of the fact those elements in positions 1 through - 1 are already known in the sorted order.

Void insertion_sort( input_type a[ ], unsigned int n )

{

unsigned int j, p;

input_type tmp;

a[0] = MIN_DATA;        /* sentinel */

for( p=2; p <= n; p++ )

{

tmp = a[p];

for( j = p; tmp < a[j-1]; j-- )

a[j] = a[j-1];

a[j] = tmp;

}

}

Because of the nested loops present, each of which can take iterations, insertion sort is O(n2). Furthermore, this bound is tight, because input in reverse order can actually obtain this bound. A precise calculation shows that the test at line 4 can be executed at most of the times for each value of p. By summing over all gives a total of (n(n-1))/2 = O(n2).

 

Posted Date: 7/10/2012 5:59:56 AM | Location : United States







Related Discussions:- Explain insertion sort, Assignment Help, Ask Question on Explain insertion sort, Get Answer, Expert's Help, Explain insertion sort Discussions

Write discussion on Explain insertion sort
Your posts are moderated
Related Questions
The disadvantages or limitations of the last in first out costing method are: The election of last in first out for income tax purposes is binding for all subsequent yea

Records are mapped onto a computer store by simply juxtaposing their elements. The address of a component (field) r relative to the origin address of the record r is named the fiel

Give an algorithm to find both the maximum and minimum of 380 distinct numbers that uses at most 568 comparisons.

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know

characteristics of a good algorithm

Post-order Traversal This can be done both iteratively and recursively. The iterative solution would need a change of the in-order traversal algorithm.

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an