Question
  1. Insertion Sort
03 Nov 2017
Answer :
Word Count : 615

We can give a more precise analysis of the operation of insertion sort. It is going to be a bit complicated. We will find out in the next section that insertion sort is not a very good sorting method and should not be used except in special circumstances. So why waste time on a complicated analysis? Simply because it happens to be a reasonably nice piece of mathematics from which you might learn something.

 

The important quantity in the analysis of the timing of Insertion Sort is the total distance through which the elements of the list are moved to the right during the sort. Let us assume, as usual, that we are dealing with a permutation of (1, 2,..., n).

 

By the nature of the algorithm, the number of places that i is moved in the sort is equal to the number of elements that are less than i and to the right of i in the original list. For example, if you apply insertion sort to the list

 

= (7, 4, 5, 1, 3, 2, 6)

you will find that 1,2 and 6 do not get moved at all, 3 is moved one place (2 is less than it), 5 is moved 3 places (1,3,2

_________ _________ ________ _____ ___.
_________ ____ _______ ________ ___ ____ ________ ___ ________.
________ _____ ________ ______ _________ _______ _______ _____ _________.
_____ ____ _______ _______ _______ _______ ______ ________.
_________ ___ ___ ________ _____ _____ _________ ____ _________ __________.
____ ___ ____ _____ ____ _________ _________ ________ _____ __________.
______ _________ ___ _____ ___ ________ ___.
_____ _______ ___ __________ _____ __________ _________ ______ _____ _____ ____.
_______ _________ _________ __________ _______ ________ _______ ____ ____ __________.
_______ _____ ___ _______ ____ ________ __________ ____ ______ __________ _________ ______.
____ _________ ________ _____ ______ ______ _______ _________ ___ ______.
________ ________ _____ _____ ______ ________ _______.
________ ____ ______ ______ ____ _________ ______ _____ ________ _________.
_______ ______ ________ _____ _______ _________.
_______ ______ _________ ______ ________ __________.
________ _____ _________ _________ _________ _________.
_______ ___ ______ _____ _____ _________ _________ ______ ______ ________ __________.
______ ___ ___ ___ _______ ____.
_____ ______ __________ __________ __________.
_____ ________ ______ ___ _____ ________ _______ ____ _________.
_____ _______ ___ ____ ______ ___ ______ __________ ________ _________ ________.
_____ _______ ____ ______ ____ ________.
_______ ______ _____ __________ _______ _______ ______ ______.
______ ______ _______ _______ _______ _______ _____ ____ _____.
__________ ____ ________ __________ ______.
________ __________ ______ _____ ____ _________ __________.
________ _____ ________ ___ ______.
______ ______ ________ ___ ______ _______ ________ _______ _______ __________ _______ _____.
______ _______ __________ ________ _________ _____ __________ ______ ___ _________ _____.
________ _____ _____ _____ __________ __________ _________ ________ _______ __________ ______.
__________ ____ ____ ____ __________ ____.
____ _____ __________ _____ _____ _____ _________ _______ ______ ___ ___ __________.
_______ _____ __________ ______ _______ ______.
_____ _________ ________ ______ _____ _________.
________ _________ ______ ___ __________.
________ _______ ________ ___ _____ ___ ____ ______ ___ _________.
________ ______ ___ ______ _____ _________.
___ ________ _________ _______ _______ ______ _________ _____ _______ _____ _______ ________.
_____ ___ ________ ______ ___ _______.
__________ _________ _______ ______ __________ ______ ________ ________ _____.
___ ______ ________ _________ ___ ______ __________ ________ _______ _________.
_____ _____ ________ _________ ______ ____ _______ ___.
_____ ________ ___ ________ ________.
__________ _______ ____ ___ _____ _______ _____ _________ _____ ______.
___ ________ ______ ____ ____ ______ _________ __________ ___.
__________ _______ _________ ______ ___ ___ _____ _______ ________ ____.
_____ ____ ________ ____ ______ ______ __________ _______ ______ _____ ______.
__________ _____ ____ _________ _______ _________ __________.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU MCS 31 2011 - Insertion Sort | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→