1

2
3
4
5
6
7
8
34 8 64 51 32 21 Initial State

9
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

10
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

After pass 2 8 34 64 51 32 21 64 moved 0 positions

11
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

After pass 2 8 34 64 51 32 21 64 moved 0 positions

After pass 3 8 34 51 64 32 21 51 moved 1 position

12
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

After pass 2 8 34 64 51 32 21 64 moved 0 positions

After pass 3 8 34 51 64 32 21 51 moved 1 position

After pass 4 8 32 34 51 64 21 32 moved 3 positions

13
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

After pass 2 8 34 64 51 32 21 64 moved 0 positions

After pass 3 8 34 51 64 32 21 51 moved 1 position

After pass 4 8 32 34 51 64 21 32 moved 3 positions

After pass 5 8 21 32 34 51 64 21 moved 4 positions

14
INSERTION SORT
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
// loop over the passes
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
// loop over the elements
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
}
Sorting Algorithms Demo
5 Sorting Algorithms in 6 Minutes (movie)
Insertion Sort Animation
15
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
}
Loop for the passes
16
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
}
Remember the element a[p] in the tmp variable
17
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
} Keep on moving elements toward right
} (to open up a hole for a[p]) until either
j=0 or
tmp is  a[j – 1]
18
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
}
Finally place a[p] in the hole found.
19
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
} Analysis:
This test is executed at most p times for each value of p.

Total Comparisons =

20
template <class Comparable>
void insertionSort (vector <Comparable> & a)
{
int j;
for (int p = 1; p < a.size(); p++)
{
Comparable tmp = a[p];
for (j = p; j > 0 && tmp < a[j – 1]; j ––)
a[j] = a[j –1];
a[j] = tmp;
}
}
Analysis:
If the input is already sorted (or almost sorted) the algorithm
is very fast since the test will fail immediately!
21
22
 34 8 64 51 32 21 Initial State
0 1 2 3 4 5

After pass 1 8 34 64 51 32 21 8 moved 1 position

After pass 2 8 34 64 51 32 21 64 moved 0 positions

After pass 3 8 34 51 64 32 21 51 moved 1 position

After pass 4 8 32 34 51 64 21 32 moved 3 positions

After pass 5 8 21 32 34 51 64 21 moved 4 positions

23
24
25
26
27
28
29
30
31
32
33
 0 1 2 3 4 5 6 7 8 9 10 11 12

81 94 11 96 12 35 17 95 28 58 41 75 15

After h=5-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

35 17 11 28 12 41 75 15 96 58 81 94 95

Sequence of increments: 1, 3, 5 34
 0 1 2 3 4 5 6 7 8 9 10 11 12

81 94 11 96 12 35 17 95 28 58 41 75 15

After h=5-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

35 17 11 28 12 41 75 15 96 58 81 94 95

After h=3-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

28 12 11 35 15 41 58 17 94 75 81 96 95

Sequence of increments: 1, 3, 5 35
 0 1 2 3 4 5 6 7 8 9 10 11 12

81 94 11 96 12 35 17 95 28 58 41 75 15

After h=5-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

35 17 11 28 12 41 75 15 96 58 81 94 95

After h=3-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

28 12 11 35 15 41 58 17 94 75 81 96 95

After h=1-sort
0 1 2 3 4 5 6 7 8 9 10 11 12

11 12 15 17 28 35 41 58 75 81 94 95 96

Sequence of increments: 1, 3, 5 36
37
 SHELLSORT
template <class Comparable>
void shellsort (vector <Comparable> & a)
{
int j;
// Loop over increments
for (int gap = a.size()/2; gap > 0; gap/=2)
// Loop over elements
for (int i = gap; i < a.size(); i++)
{
Comparable tmp = a[i];
// Loop over elements that are gap apart
for (j = i; j >= gap && tmp < a[j – gap]; j –= gap)
a[j] = a[j –gap];
a[j] = tmp;
}
}
Shell Sort Animation-1 Shell Sort Animation-2
Sorting Algorithms Demo 38
39
40
41
42
N / 2

i 1

i 1

43
 1
2
N
O(  )  O( N )  O( N )
t t
2
2

h h
i 1 i 1

i i
44
45
46