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 n - 1 passes. For pass p = 2 through n, insertion sort assures that the elements in the positions 1 through p are in sorted order. Insertion sort makes use of the fact those elements in positions 1 through p - 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 n 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 p times for each value of p. By summing over all p gives a total of (n(n-1))/2 = O(n2).

 

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

Ask an Expert

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

Write your message here..

Related Questions

Numerical - algorithm, Q. What is the smallest value of n such that an algo... 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

Green computing, In the present scenario of global warming, the computer ha... 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

How to improve my 69 algorithm, How can i decrease my latency for 69 moves How can i decrease my latency for 69 moves

Structures for complete undirected graphs, Q. Draw  the structures of compl... 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, How do collisions happen during ha... 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

Insert an element after an element pointed by some pointer, Consider a link... 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, Representation of Linked list in M... 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, Explain about Hidden-surface Hidden-line... 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

Single pointer pointing to the tail of the queue, Can a Queue be shown by c... 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

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