Design and Analysis of
Algorithm
Unit 2: Analysis of Algorithms(II)
Insertion Sort, Selection Sort, Bubble Sort,
Radix Sort
Compiled By
Prof. Dharmesh R. Tank
CE\IT Department, LDRP-ITR
The Sorting Problem
• Input:
– A sequence of n numbers a1, a2, . . . , an
• Output:
– A permutation (reordering) a1’, a2’, . . . , an’ of the input
sequence such that a1’ ≤ a2’ ≤ · · · ≤ an’
Structure of data
Why Study Sorting Algorithms?
• There are a variety of situations that we can
encounter
– Do we have randomly ordered keys?
– Are all keys distinct?
– How large is the set of keys to be ordered?
– Need guaranteed performance?
• Various algorithms are better suited to some of
these situations
Some Definitions
• Internal Sort
– The data to be sorted is all stored in the computer’s
main memory.
• External Sort
– Some of the data to be sorted might be stored in
some external, slower, device.
• In Place Sort
– The amount of extra space required to sort the data is
constant with the input size.
Stability
• A STABLE sort preserves relative order of records with
equal keys
Sorted on first key:
Sort file on second key:
Records with key value
3 are not in order on
first key!!
Insertion Sort
• Idea: like sorting a hand of playing cards
– Start with an empty left hand and the cards facing
down on the table.
– Remove one card at a time from the table, and insert
it into the correct position in the left hand
• compare it with each of the cards already in the hand, from
right to left
– The cards held in the left hand are sorted
• these cards were originally the top cards of the pile on the
table
Insertion Sort
To insert 12, we
need to make
room for it by
6 10 24 36 moving first 36
and then 24.
12
Insertion Sort
6 10 24 36
12
Insertion Sort
6 10 24 3
6
12
Insertion Sort
10 12 24
6 36
Insertion Sort
Input Array
5 2 4 6 1
3
at each iteration, the array is divided in two sub-arrays:
left sub-array right sub-array
sorted unsorted
Insertion Sort
Insertion Sort
Alg.: INSERTION-SORT(A) 1 2 3 4 5 6 7 8
a1 a2 a3 a4 a5 a6 a7 a8
for j ← 2 to n
do key ← A[ j ] key
Insert A[ j ] into the sorted sequence A[1 . . j -1]
i←j-1
while i > 0 and A[i] > key
do A[i + 1] ← A[i]
i←i–1
A[i + 1] ← key
• Insertion sort – sorts the elements in place
Loop Invariant for Insertion Sort
Alg.: INSERTION-SORT(A)
for j ← 2 to n
do key ← A[ j ]
Insert A[ j ] into the sorted sequence A[1 . . j -1]
i←j-1
while i > 0 and A[i] > key
do A[i + 1] ← A[i]
i←i–1
A[i + 1] ← key
Invariant: at the start of the for loop the elements in A[1 . . j-1]
are in sorted order
Analysis of Insertion Sort
INSERTION-SORT(A) cost times
for j ← 2 to n c1 n
do key ← A[ j ] c2 n-1
Insert A[ j ] into the sorted sequence A[1 . . j -1] 0 n-1
i←j-1 c4 n-1n
while i > 0 and A[i] > key c5 j 2 j
t
n
do A[i + 1] ← A[i] (t j 1)
c6 j 2
n
i←i–1 (t j 1)
c7 j 2
A[i + 1] ← key
c8 n-1
tj: # of times the while statement is executed at iteration j
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Best Case Analysis
• The array is already sorted “while i > 0 and A[i] > key”
– A[i] ≤ key upon the first time the while loop test is run
(when i = j -1)
– tj = 1
• T(n) = c1n + c2(n -1) + c4(n -1) + c5(n -1) + c8(n-1) =
(c1 + c2 + c4 + c5 + c8)n + (c2 + c4 + c5 + c8)
= an + b = (n) or Ω(n)
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Worst Case Analysis
• The array is in reverse sorted order “while i > 0 and A[i] > key”
– Always A[i] > key in while loop test
– Have to compare key with all elements to the left of the j-th
position compare with j-1 elements tj = j
n
n(n 1) n
n(n 1) n
n(n 1)
using
j 1
j
2
j
j 2 2
1 ( j 1)
j 2 2
we have:
n( n 1) n (n 1) n( n 1)
T ( n ) c1n c2 ( n 1) c4 ( n 1) c5 1 c6 c7 c8 ( n 1)
2 2 2
an 2 bn c a quadratic function of n
• T(n) = (n2) order of growth in n2
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Insertion Sort - Summary
• Advantages
– Good running time for “almost sorted” arrays (n)
– Best case (n) or Ω(n) when array is sorted or single
element in the list.
• Disadvantages
– (n2) or O(n2) running time in worst and average
case
Bubble Sort
• Idea:
– Repeatedly pass through the array
– Swaps adjacent elements that are out of order
i
1 2 3 n
8 4 6 9 2 3 1
j
• Easier to implement, but slower than Insertion
sort
Example
8 4 6 9 2 3 1 1 8 4 6 9 2 3
i=1 j i=2 j
8 4 6 9 2 1 3 1 2 8 4 6 9 3
i=1 j i=3 j
8 4 6 9 1 2 3 1 2 3 8 4 6 9
i=1 j i=4 j
8 4 6 1 9 2 3 1 2 3 4 8 6 9
i=1 j i=5 j
8 4 1 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=6 j
8 1 4 6 9 2 3 1 2 3 4 6 8 9
i=1 j i=7
j
1 8 4 6 9 2 3
i=1 j
Bubble Sort
Alg.: BUBBLESORT(A)
for i 1 to length[A]
do for j length[A] downto i + 1
do if A[j] < A[j -1]
then exchange A[j] A[j-1]
i
8 4 6 9 2 3 1
i=1 j
Analysis of Bubble Sort
Alg.: BUBBLESORT(A) cost times
C1 (n+1)
for i 1 to length[A]
C2
do for j length[A] downto i + 1
do if A[j] < A[j -1] C3
then exchange A[j] A[j-1] C4
n n n
T(n) = c1(n+1) + c2 (n i 1) c3 (n i ) c4 (n i)
i 1
i 1 n i 1
= (n) + (c2 + c2 + c4) (n i)
i 1
n n n
n ( n 1) n 2
n
where (n i ) n i n
2
i 1 i 1 i 1 2 2 2
Thus, T(n) = (n2)
Best Case Analysis
• The array is already sorted “while i > 0 and A[i] > key”
– A[i] ≤ key upon the first time the while loop test is run
(when i = j -1)
– tj = 1
• T(n) = c1n + c2(n -1) + c4(n -1) + c5(n -1) + c8(n-1) =
(c1 + c2 + c4 + c5 + c8)n + (c2 + c4 + c5 + c8)
= an + b = (n) or Ω(n)
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Worst Case Analysis
• The array is in reverse sorted order “while i > 0 and A[i] > key”
– Always A[i] > key in while loop test
– Have to compare key with all elements to the left of the j-th
position compare with j-1 elements tj = j
n
n(n 1) n
n(n 1) n
n(n 1)
using
j 1
j
2
j
j 2 2
1 ( j 1)
j 2 2
we have:
n( n 1) n (n 1) n( n 1)
T ( n ) c1n c2 ( n 1) c4 ( n 1) c5 1 c6 c7 c8 ( n 1)
2 2 2
an 2 bn c a quadratic function of n
• T(n) = (n2) order of growth in n2
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Bubble Sort - Summary
• Advantages
– Good running time for “almost sorted” arrays (n)
– Best case (n) or Ω(n) when array is sorted or single
element in the list.
– For best case, starting with pass one, there is no
exchange of data occur.
• Disadvantages
– (n2) or O(n2) running time in worst and average
case
Selection Sort
• Idea:
– Find the smallest element in the array
– Exchange it with the element in the first position
– Find the second smallest element and exchange it with
the element in the second position
– Continue until the array is sorted
• Disadvantage:
– Running time depends only slightly on the amount of
order in the file
Example
8 4 6 9 2 3 1 1 2 3 4 9 6 8
1 4 6 9 2 3 8 1 2 3 4 6 9 8
1 2 6 9 4 3 8 1 2 3 4 6 8 9
1 2 3 9 4 6 8 1 2 3 4 6 8 9
Selection Sort
Alg.: SELECTION-SORT(A)
n ← length[A] 8 4 6 9 2 3 1
for j ← 1 to n - 1
do smallest ← j
for i ← j + 1 to n
do if A[i] < A[smallest]
then smallest ← i
exchange A[j] ↔ A[smallest]
Analysis of Selection Sort
Alg.: SELECTION-SORT(A) cost times
n ← length[A] c1 1
for j ← 1 to n - 1 c2 n
do smallest ← j
c3 n-1
for i ← j + 1 to n
n 1
(n j 1)
c4 j 1
do if A[i] < A[smallest]
n 1
(n j )
c5
j 1
then smallest ← i
n 1
j 1
(n j )
exchange A[j] ↔ A[smallest] c6
T (n) c1 c2 n c3 (n 1) c4 (n j 1) c5 n j c6 n j cc77 (n 1) n-1
n 1 n 1 n 1
(n 2 )
j 1 j 1 j 2
Worst Case Analysis
• The array is in reverse sorted order “while i > 0 and A[i] > key”
– Always A[i] > key in while loop test
– Have to compare key with all elements to the left of the j-th
position compare with j-1 elements tj = j
n
n(n 1) n
n(n 1) n
n(n 1)
using
j 1
j
2
j
j 2 2
1 ( j 1)
j 2 2
we have:
n( n 1) n (n 1) n( n 1)
T ( n ) c1n c2 ( n 1) c4 ( n 1) c5 1 c6 c7 c8 ( n 1)
2 2 2
an 2 bn c a quadratic function of n
• T(n) = (n2) order of growth in n2
T (n) c1n c2 (n 1) c4 (n 1) c5 t j c6 t j 1 c7 t j 1 c8 (n 1)
n n n
j 2 j 2 j 2
Selection Sort - Summary
• Advantages
– Good running time for “almost sorted” arrays (n)
– Best case (n2) or Ω(n2) when array is sorted or
single element in the list.
• Disadvantages
– (n2) running time in worst and average case
