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
Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.    A n

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the


Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? O (1)

Representation of Linked list in Memory:- Each node has an info part and a pointer to the next node also known as link. The number of pointers is two in case of doubly linked

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

How branching takes place in Instruction pipeline. Explain with suitable examples