CS代考 COMP90038

COMP90038
Algorithms and Complexity
Lecture 9: Decrease-and-Conquer-by-a-Constant (with thanks to Harald Søndergaard)

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
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
5 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

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 j ≥ 0 and v < A[j] to just 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. 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? yes ? Very good for small arrays (say, a couple of hundred • 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: 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 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? yes yes Very good for small arrays (say, a couple of hundred • elements). 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 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 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. 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 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 • • In-place? yes no 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? 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!