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. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

a) Find the shortest paths from r to all other nodes in the digraph G=(V,E) shown below using the Bellman-Ford algorithm (as taught in class). Please show your work, and draw the f

what is alphanumerical code

Q. Write an algorithm INSERT which takes a pointer to a sorted list and a pointer to a node and inserts the node into its correct position or place in the list.  Ans: /* s

Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

Q. Explain any three methods or techniques of representing polynomials using arrays. Write which method is most efficient or effective for representing the following polynomials.

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci