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

Accept a file and form a binary tree - huffman encoding, Huffman Encoding i... Huffman Encoding is one of the very simple algorithms to compress data. Even though it is very old and simple , it is still widely used (eg : in few stages of JPEG, MPEG etc). In t

Queue be represented by circular linked list, Q. Can a Queue be represented... Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

Design a binary search tree, Binary Search Tree usage: Write a progra... Binary Search Tree usage: Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Specically, your program should do the

Infix to postfix conversion, A*(B+D)/E-F*(G+H/K) A*(B+D)/E-F*(G+H/K)

Example of binary search, Let us assume a file of 5 records that means n = ... Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

Estimate cost of an optimal diapath, Normally a potential y satisfies y r ... Normally a potential y satisfies y r = 0 and 0 ³ y w - c vw -y v . Given an integer K³0, define a K-potential to be an array y that satisfies yr = 0 and K ³ y w - c vw -y v

Define a sparse metrics, Define a sparse metrics. A matrix in which num... Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

How conquer technique can be applied to binary trees, How divide and conque... How divide and conquer technique can be applied to binary trees?  As the binary tree definition itself separates a binary tree into two smaller structures of the similar type,

Decision tree - id3 algorithm, Decision Tree - ID3 algorithm: Imagine ... Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

Exlain double linked list, Double Linked List In a doubly linked list, ... Double Linked List In a doubly linked list, also known as 2 way lists, each node is separated into 3 parts. The first part is called last pointer field. It has the address of t