COMP90038
Algorithms and Complexity
Lecture 9: Decrease-and-Conquer-by-a-Constant
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Decrease-and-Conquer-
by-a-Constant
In this approach, the size of the problem is reduced by some constant in each iteration of the algorithm.
•
A simple example is the following approach to
•
sorting: To sort an array of length n, just
1. sort the first n − 1 items, then
2. locate the cell that should hold the last item, shift all elements to its right to the right, and place the last element.
Sorting n items
A:
0123456
23
9
52
12
41
83
46
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
Sort first n-1 items
23
9
52
12
41
83
46
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
Sort first n-1 items
23
9
52
12
41
83
46
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
4 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
46
52
83
5 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
9
12
23
41
52
83
46
v: 46
6 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
46
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
83
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
83
83
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
52
83
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
52
52
83
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
46
52
83
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Sorting n items
A:
0123456
A[j] v: 46
9
12
23
41
46
52
83
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort
Sorting an array A[0]..A[n − 1]:
•
To sort A[0] .. A[i] first sort A[0] .. A[i-1], then insert A[i] in
•
its proper place
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Complexity of Insertion Sort
The for loop is traversed n − 1 times. In the ith round, the test v < A[j] is performed i times, in the worst case.
Hence the worst-case running time is
What does input look like in the worst case?
•
•
•
Complexity of Insertion Sort
The for loop is traversed n − 1 times. In the ith round, the test v < A[j] is performed i times, in the worst case.
Hence the worst-case running time is
What does input look like in the worst case?
•
•
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
Complexity of Insertion Sort
The for loop is traversed n − 1 times. In the ith round, the test v < A[j] is performed i times, in the worst case.
Hence the worst-case running time is
What does input look like in the worst case?
•
•
14
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
15
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The Trick of Posting
a Sentinel
If we are sorting elements from a domain that is bounded from below, that is, there is a minimal element min, and the array A was known to have a free cell to the left of A[0], then we could simplify the test. Namely, we would place min (a sentinel) in that cell (A[−1]) and change the test from
•
•
•
v < A[j]
That will speed up insertion sort by a constant factor.
For this reason, extreme array cells (such as A[0] in C, and/or A[n + 1]) are sometimes left free deliberately, so that they can be used to hold sentinels; only A[1] to A[n] hold proper data.
to just
j ≥ 0 and v < A[j]
Posting a Sentinel
A:
0123456
A[j]
Test required: j ≥ 0 and v < A[j]
9
23
52
12
41
83
46
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Posting a Sentinel
A:
01234567
A[j] Test required: v < A[j]
-1
9
23
52
12
41
83
46
17 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
• • • •
• •
In-place?
Stable?
Very good for small arrays (say, a couple of hundred
•
elements).
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
Very good for small arrays (say, a couple of hundred
• • • •
•
elements).
• •
In-place? yes
Stable?
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
• • • •
• •
Stable?
?
Very good for small arrays (say, a couple of hundred In-place? yes
•
elements).
Insertion Sort Stability
key: 4 val: ab
key: 3 val: bc
key: 4 val: de
key: 3 val: fg
0123
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
key: 4 val: ab
key: 3 val: bc
key: 4 val: de
key: 3 val: fg
0123
19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
key: 3 val: bc
key: 4 val: ab
key: 4 val: de
key: 3 val: fg
0123
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
key: 3 val: bc
key: 4 val: ab
key: 4 val: de
key: 3 val: fg
0123
20 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
key: 3 val: bc
key: 3 val: fg
key: 4 val: ab
key: 4 val: de
0123
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Insertion Sort Stability
key: 3 val: bc
key: 3 val: fg
key: 4 val: ab
key: 4 val: de
0123
21 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Stable
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
• • • •
• •
In-place?
Stable?
Very good for small arrays (say, a couple of hundred
•
elements).
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
Very good for small arrays (say, a couple of hundred
• • • •
•
elements).
• •
In-place? yes
Stable?
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Insertion Sort
Easy to understand and implement.
Average-case and worst-case complexity both quadratic.
However, linear for almost-sorted input.
Some cleverer sorting algorithms perform almost-sorting and then let insertion sort take over.
• • • •
• •
Stable?
yes
Very good for small arrays (say, a couple of hundred In-place? yes
•
elements).
Shellsort: Motivation
A:
0123456
9
8
7
6
5
4
3
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
A:
0123456
A:
0123456
9
8
7
6
5
4
3
8
9
7
6
5
4
3
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
A:
0123456
A:
0123456
A:
0123456
9
8
7
6
5
4
3
8
9
7
6
5
4
3
7
8
9
6
5
4
3
23 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
A:
0123456
A:
0123456
A:
0123456
It would be better if we could move the 9, 8, etc.
to the right faster
9
8
7
6
5
4
3
8
9
7
6
5
4
3
7
8
9
6
5
4
3
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
A:
0123456
9
8
7
6
5
4
3
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the yellow entries
A:
0123456
9
8
7
6
5
4
3
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the yellow entries
A:
0123456
A:
0123456
9
8
7
6
5
4
3
6
8
7
9
5
4
3
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the yellow entries
A:
0123456
A:
0123456
A:
0123456
9
8
7
6
5
4
3
6
8
7
9
5
4
3
3
8
7
6
5
4
9
24 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
A:
0123456
3
8
7
6
5
4
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
3
8
7
6
5
4
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
3
8
7
6
5
4
9
3
5
7
6
8
4
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
Sort the pink entries
3
8
7
6
5
4
9
3
5
7
6
8
4
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
Sort the pink entries
A:
0123456
3
8
7
6
5
4
9
3
5
7
6
8
4
9
3
5
4
6
8
7
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
Sort the pink entries
A:
0123456
Notice how it is now almost sorted
3
8
7
6
5
4
9
3
5
7
6
8
4
9
3
5
4
6
8
7
9
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
Sort the pink entries
A:
0123456
Notice how it is now almost sorted
3
8
7
6
5
4
9
3
5
7
6
8
4
9
3
5
4
6
8
7
9
Now do a final round of insertion sort over the entire array
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Motivation
Sort the blue entries
A:
0123456
A:
0123456
Sort the pink entries
A:
0123456
Notice how it is now almost sorted
3
8
7
6
5
4
9
3
5
7
6
8
4
9
3
5
4
6
8
7
9
Now do a final round of insertion sort over the entire array
A:
3
4
5
6
7
8
9
0123456
25 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort
We just did a shellsort for k=3 In general:
Think of the array as an interleaving of k lists Sort each list separately using insertion sort
•
•
•
•
Then sort the resulting entire array using a final
•
pass of insertion sort
27
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort Passes and Gap Sequences
For large files, start with larger k and then repeat with It is common to start from somewhere in the sequence
what is the sequence?
•
smaller ks
•
1, 4, 13, 40, 121, 364, 1093, ... and work backwards.
•
For example, for an array of size 20,000, start by 364-
•
sorting, then 121-sort, then 40-sort, and so on.
•
Sequences with smaller gaps (a factor of about 2.3) appear to work better, but nobody really understands why.
Properties of Shellsort
Fewer comparisons than insertion sort. Known to
•
be worst-case O(n n) for good gap sequences.
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Conjectured to be O(n1.25) but the algorithm is very Very good on medium-sized arrays (up to size
In-place? Stable?
•
hard to analyse.
•
10,000 or so).
• •
Properties of Shellsort
Fewer comparisons than insertion sort. Known to
•
be worst-case O(n n) for good gap sequences.
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Conjectured to be O(n1.25) but the algorithm is very Very good on medium-sized arrays (up to size
In-place? yes Stable?
•
hard to analyse.
•
10,000 or so).
• •
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
• •
In-place? yes
?
Fewer comparisons than insertion sort. Known to
•
be worst-case O(n n) for good gap sequences.
Conjectured to be O(n1.25) but the algorithm is very Very good on medium-sized arrays (up to size
•
hard to analyse.
•
10,000 or so).
Stable?
Shellsort: Stability
A:
0123456
1
7
4
6
4
8
9
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
A:
0123456
1
7
4
6
4
8
9
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
after sorting the blues
Shellsort: Stability
A:
0123456
A:
0123456
after sorting the blues
1
7
4
6
4
8
9
1
4
4
6
7
8
9
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Shellsort: Stability
A:
0123456
A:
0123456
after sorting the blues
1
7
4
6
4
8
9
1
4
4
6
7
8
9
relative order of the two 4s has changed!
29 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
30
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
Fewer comparisons than insertion sort. Known to
•
be worst-case for good gap sequences.
Conjectured toOb(en On(n) 1.25) but the algorithm is very Very good on medium-sized arrays (up to size
In-place? Stable?
•
hard to analyse.
•
10,000 or so).
• •
30
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Properties of Shellsort
Fewer comparisons than insertion sort. Known to
•
be worst-case for good gap sequences.
Conjectured toOb(en On(n) 1.25) but the algorithm is very Very good on medium-sized arrays (up to size
In-place? yes Stable?
•
hard to analyse.
•
10,000 or so).
• •
Properties of Shellsort
Fewer comparisons than insertion sort. Known to
•
be worst-case for good gap sequences.
Conjectured toOb(en On(n) 1.25) but the algorithm is very Very good on medium-sized arrays (up to size
30
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
•
hard to analyse.
•
10,000 or so).
• •
In-place? yes
no
Stable?
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Other Instances of Decrease-and- Conquer by a Constant
Insertion sort is a simple instance of the “decrease-
•
and-conquer by a constant” approach.
Another is the approach to topological sorting that
•
repeatedly removes a source.
•
In the next lecture we look at examples of “decrease by some factor”, leading to methods with logarithmic time behaviour or better!