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
RENDERING, SHADING AND COLOURING By introducing hidden line removal we have already taken one step away from wire-frame drawings towards being able to realistically model and d

Q. Which are the two standard ways of traversing a graph?  Explain them with an example of each.  Ans:   T he two ways of traversing a graph are written below

Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c

explain quick sort algorithm

Q. How do we represent a max-heap sequentially? Explain by taking a valid   example.         Ans: A max heap is also called as a descending heap, of size n is an almos


Q. Write down the recursive function to count the number of the nodes in the binary tree.    A n s . R ecursive Function to count no. of Nodes in Binary Tree is writt

A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.