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
A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

State the ways to construct container taxonomy There are several ways that we could construct our container taxonomy from here; one way that works well is to make a fundamental

For the following graph find the adjacency matrix and adjacency list representation of the graph.

how to reduce the number of passes in selection sort

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

What are stacks? A stack is a data structure that organizes data similar to how one organizes a pile of coins. The new coin is always placed on the top and the oldest is on the

Q. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.