Scribd
Upload
19 views30 pages

Insertion Sort Analysis and Advantages

The document discusses insertion sort, an algorithm for sorting a list of values. Insertion sort works by building a sorted sequence from one element at a time. It inserts each subsequent element into the correct position in the already sorted sequence. This process is repeated until the entire list is sorted. The time complexity of insertion sort is O(n^2) as in the worst case, inserting each new element requires searching through the entire sorted portion which can be up to n elements long. While O(n^2) sorting is inefficient for large n, insertion sort performs better than other O(n^2) algorithms like selection sort when the input is close to sorted.

Uploaded by

smitha bhat
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views30 pages

Insertion Sort Analysis and Advantages

The document discusses insertion sort, an algorithm for sorting a list of values. Insertion sort works by building a sorted sequence from one element at a time. It inserts each subsequent element into the correct position in the already sorted sequence. This process is repeated until the entire list is sorted. The time complexity of insertion sort is O(n^2) as in the worst case, inserting each new element requires searching through the entire sorted portion which can be up to n elements long. While O(n^2) sorting is inefficient for large n, insertion sort performs better than other O(n^2) algorithms like selection sort when the input is close to sorted.

Uploaded by

smitha bhat
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

NPTEL MOOC,JAN-FEB 2015

Week 2, Module 4

DESIGN AND ANALYSIS



OF ALGORITHMS
Insertion Sort

MADHAVAN MUKUND, CHENNAI MATHEMATICAL INSTITUTE


[Link]
Sorting
Searching for a value

Unsorted array — linear scan, O(n)

Sorted array — binary search, O(log n)

Other advantages of sorting

Finding median value: midpoint of sorted list

Checking for duplicates

Building a frequency table of values


How to sort?

You are a Teaching Assistant for a course

The instructor gives you a stack of exam answer


papers with marks, ordered randomly

Your task is to arrange them in descending order


Strategy 2
First paper: put in a new stack

Second paper:

Lower marks than first? Place below first paper



Higher marks than first? Place above first paper

Third paper

Insert into the correct position with respect to first


two papers

Do this for each subsequent paper:



insert into correct position in new sorted stack
Strategy 2 …

74 32 89 55 21 64
Strategy 2 …

74 32 89 55 21 64

74
Strategy 2 …

74 32 89 55 21 64

32 74
Strategy 2 …

74 32 89 55 21 64

32 74 89
Strategy 2 …

74 32 89 55 21 64

32 55 74 89
Strategy 2 …

74 32 89 55 21 64

21 32 55 74 89
Strategy 2 …

74 32 89 55 21 64

21 32 55 64 74 89
Strategy 2 …

Insertion Sort

Start building a sorted sequence with one element

Pick up next unsorted element and insert it into its


correct place in the already sorted sequence
Insertion Sort
InsertionSort(A,n) // Sort A of size n

for (pos = 1; pos < n; pos++)



// Build longer and longer sorted segments

// In each iteration A[0]..A[pos-1] is already sorted

// Move first element after sorted segment left



// till it is in the correct place

nextpos = pos

while (nextpos > 0 && 

A[nextpos] < A[nextpos-1])

swap(A,nextpos,nextpos-1)

nextpos = nextpos-1
Insertion Sort

74 32 89 55 21 64
Insertion Sort

74 32 89 55 21 64
Insertion Sort

32 74 89 55 21 64
Insertion Sort

32 74 89 55 21 64
Insertion Sort

32 74 55 89 21 64
Insertion Sort

32 55 74 89 21 64
Insertion Sort

32 55 74 21 89 64
Insertion Sort

32 55 21 74 89 64
Insertion Sort

32 21 55 74 89 64
Insertion Sort

21 32 55 74 89 64
Insertion Sort

21 32 55 74 64 89
Insertion Sort

21 32 55 64 74 89
Analysis of Insertion Sort

Inserting a new value in sorted segment of length


k requires upto k steps in the worst case

In each iteration, sorted segment in which to insert


increased by 1

t(n) = 1 + 2 + … + n-1 = n(n-1)/2 = O(n2)


Recursive formulation
Assume

A[0…i-1] is already sorted

A[i…n-1] is yet to be sorted

Insert A[i] in A[0..i-1]

Recursively sort A[i+1…n-1]

Base case: i = n-1


Insertion Sort, recursive
InsertionSort(A,start,n) // Sort A from start to n-1

if (start >= n-1)



return;

Insert(A,start);

InsertionSort(A,start+1,n);

return;

Insert(A,start) // Insert A[start] into A[0..start-1]

pos = start;

while (pos > 0 && A[pos] < A[pos-1])

swap(A,pos,pos-1);

pos = pos-1;
Recurrence
t(n), time to run insertion sort on length n

Time t(n-1) to sort segment A[0] to A[n-2]

n-1 steps to insert A[n-1] in sorted segment

Recurrence

t(n) = n-1 + t(n-1)



t(1) = 1

t(n) = n-1 + t(n-1) = n-1 + ((n-2) + t(n-2)) = … =



(n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2)
O(n )
2 sorting algorithms
Selection sort and insertion sort are both O(n2)

So is bubble sort, which we will not discuss here

O(n2) sorting is infeasible for n over 10000

Among O(n2) sorts, insertion sort is usually better


than selection sort and both are better than
bubble sort

What happens when we apply insertion sort to


an already sorted list?

You might also like