STUDY MATERIAL:
• [CLRS] chapters 6, 7, 8, 9
• Lecture Notes 5, 6
Copyright By PowCoder代写 加微信 powcoder
▪ The Sorting Problem
➢ Some general facts
➢ QuickSort
➢ HeapSort, Heaps, Priority Queues ➢ Sorting Lower Bound
➢ Special Purpose Sorting Algorithms ▪ The Selection Problem
▪ Lower Bound Techniques
▪ Prune-&-Search
The Sorting Problem
INPUT: A sequence A= a1 , a2 ,··· , an of n arbitrary numbers. OUTPUT: A permutation (reordering) ap(1) , ap(2) ,··· , ap(n) of the
input sequence, such that ap(1) ap(2) ··· ap(n) .
Two elementary operations:
▪ Comparison between a pair of items ai and aj with =, <, >, or any logical combination thereof.
▪ Exchange: swapping the positions of a pair of items ai and aj . Definition: An inversion is a pair of numbers ai , aj in the input,
such that i < j but ai > aj (i.e., the pair is out of order). I(A) = the total # of inversions in sequence A.
In general: 0 I(A) n(n-1)/2.
Example: A=4,9,4,3,6,8,2,5. I(A)=14.
a2, a7 = 9, 2 is one of the inversions in A.
Some Basic Facts
▪ Swapping an adjacent pair of items will change the inversion count by +1, 0, or –1.
▪ Any sorting algorithm that (effectively) exchanges only adjacent pairs of items is doomed to take at least W(n2) steps in the worst case.
BubbleSort, InsertionSort, SelectionSort are in this category.
MergeSort, QuickSort, HeapSort are not.
▪ InsertionSort takes Q(n + I) time on every input, where n = # input items, and
I = # inversions in the input. Why?
This makes InsertionSort a suitable choice when the input is almost sorted (low I).
[C.A.R. Hoare, 1962]
Hoare lived in Moscow for a period of time; first as part of the U.K. Royal Navy studying modern Russian military; then as a visiting student at Moscow State University; and later on, worked for the National Physical Lab stationed in Moscow. He collaborated with the Automatic Machine Translation of Russian to English Project Group. Dictionaries were on a long magnetic tape in alphabetical order. So they would first sort the words in a sentence, then in one pass would compare it with the magnetic tape. …
For the sorting part, he first thought of BubbleSort, but soon realized it was too slow. QuickSort was the 2nd algorithm he says he thought of.
Sorting Student Homework Papers
The way I sort student homework papers by name:
▪ I first partition them into a small number of piles by initials, e.g., Pile1: A–F
Pile2: G–L Pile3: M–S Pile4: T–Z
▪ Then I sort each pile separately, possibly first partitioning them further into more refined groups, e.g., there are many names with the same initial.
▪ Then I reassemble the sorted piles in order.
Randomized QuickSort
Algorithm QuickSort(S)
Pre-Cond: input S is a finite sequence of arbitrary numbers Post-Cond: output is a permutation of S in sorted order
if |S| < 2 then return S
p a random element 3-Partition S into:
S< { x S : S= { x S : S> { x S :
S’< QuickSort(S<)
S’> QuickSort(S>) return S’< , S= , S’>
x < p } x = p } x > p }
§ pivot item, why random? § we already discussed this
§ O( |S| ) time
§ Exercise Question:
§ which recursive call first?!
S=: x=p S>: x>p
T(|S|) = T(| S< |) + T(| S> |) + Q( |S| ), T(n) = Q(1), for n=0,1.
QuickSort Running Time
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Worst-Case:
T(n) = maxi { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 } = T(n – 1) + T(0) + Q(n)
= T(n – 1) + Q(n) = Q(n2)
This occurs if at all recursion levels the selected pivot is (near) the extreme;
the largest or the smallest!
QuickSort Running Time
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Best-Case:
T(n) = mini { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 } = T(n/2) + T(n/2) + Q(n)
= 2T(n/2) + Q(n) = Q(n log n)
This occurs if at all recursion levels the selected pivot is (near) the median element!
QuickSort Running Time
S< : x < p p S> : x > p
i n – i –1
WLOG Assume: | S= | = 1. If it’s larger, it can only help! T(n) = T(i) + T(n-i-1) + Q(n), T(n) = Q(1), for n=0,1.
Expected-Case:
T(n) = avei { T(i) + T(n-i-1) + Q(n) : i = 0 .. n –1 }
= n1 T ( i ) + T ( n − i − 1 ) + Q ( n )
= n2 n−1 T(i) + Q(n) (full history recurrence already discussed)
= Q(n log n)
Full History Recurrence: QuickSort Example2: T(n)=n2n−1T(i)+n, n0 [ T(0)=0]
1. Multiply across by n (so that we can subsequently cancel out the summation):
nT(n)= 2n−1 T(i)+n2 , n0
2. Substitute n-1 for n:
T(i)+(n−1)2 , n1 nT(n) = (n+1)T(n−1) + 2n−1, n1
3. Subtract (2) from (1):
4. Rearrange:
T(n) = T(n−1) + 2n−1 , n1
5. Divide by n(n+1) to make LHS & RHS look alike:
n+1 n Q(n−1)= T(n−1),
n(n+1) 2n-1 = 3 − 1
(n−1)T(n−1)= 2
nT(n) − (n−1)T(n−1) = 2T(n−1) + 2n−1, n1
Q(n)= T(n), n+1
6. Rename:
7. Simplified recurrence:
n(n+1) n+1 n n+1 n
Harmonic number
Q(n)=Q(n−1)+ 3 −1 n1
8. Iteration: Q(n)=(3 −1)+(3 − 1 )+(3 − 1 )++(3 −1)+Q(0)=2H(n)− 3n
n+1 n n n−1 n−1 n−2 2 1 n+1 9. Finally: T(n)=(n+1)Q(n)=2(n+1)H(n)−3n=Q(nlogn).
Why Randomize?
S< : x < p
Worst-Case: Expected-Case: Best-Case:
p S> : x > p
T(n) = Q(n2) T(n) = Q(n log n) T(n) = Q(n log n)
▪ Randomization nullifies adverse effect of badly arranged input permutation. ▪ Algorithm sees the input as a random permutation.
▪ Probability that almost all random choices are the worst is nearly 1/n!
▪ FACT: Randomized QuickSort will take O(n log n) time with probability very close to 1
on every input.
(extremely low).
Heaps & Priority Queues
[J.W.J. Williams, 1964]
Binary Heap
▪ A = a binary tree with one key per node (duplicate keys allowed). ▪ Order: A satisfies the following partial order:
for every node x root[A] : key[x] key[parent(x)].
▪ Full tree node allocation scheme: nodes of A are allocated in increasing
order of level, and left-to-right within the same level.
▪ This allows array implementation, where array indices simulate tree pointers.
73 81 66 54
848 962 77 34 53 61 41 29
10 11 12 13
36 23 51 27 44 69 20 27 47 33 59 46
16 17 18 19 20 21 22 23 24 25 26 27
Array as Binary Heap
currently unused
parent A[ t/2 ] node A[t]
left child
right child
n = size[A]
Some MAX Heap Properties
▪ Root A[1] contains the maximum item.
▪ Every root-to-leaf path appears in non-increasing order.
▪ Every subtree is also max heap ordered. [Recursive structure]
▪ The key at any node is the largest among all its descendants (inclusive).
▪ (x,y) AncestorOf : A[x] A[y],
where AncestorOf = { (x,y) : node x is ancestor of node y }.
68 48 74 18 56
8 9 10 11 12
▪ A[1..n] = a max-heap.
▪ Suddenly, item A[t] increases in value. ▪ Now A is a “t upward corrupted heap”:
(x,y) AncestorOf : y t A[x] A[y].
▪ Question: how would you rearrange A to make it a max-heap again? ▪ Answer: percolate A[t] up its ancestral path.
procedure UpHeap(A, t) § O(log n) time Pre-Cond: A is a t upward corrupted heap
Post-Cond: A is rearranged into a max-heap
p t/2 § parent of t
if p = 0 or A[p] A[t] then return A[t] A[p]
UpHeap(A,p)
UpHeap Example
4 5 92 4 5 92
74 76 6 7 74 86 6 7
68 48 74 18 56
8 9 10 11 12
68 48 76 18 56
9 10 11 12
68 48 76 18 56
8 9 10 11 12
▪ A[1..n] = a max-heap.
▪ Suddenly, item A[t] decreases in value. ▪ Now A is a “t downward corrupted heap”:
(x,y) AncestorOf : x t A[x] A[y].
▪ Question: how would you rearrange A to make it a max-heap again? ▪ Answer: demote A[t] down along largest-child path.
procedure DownHeap(A, t) § O(log n) time Pre-Cond: A is a t downward corrupted heap
Post-Cond: A is rearranged into a max-heap c 2t § left child of t
if c > size[A] then return § c not part of heap if c < size[A] and A[c] < A[c+1] then c c+1 § now c is the largest child of t
if A[t] < A[c] then A[t] A[c] DownHeap(A, c)
DownHeap Example
82 76 265 92
5 92 467467
68 48 74 18 56
8 9 10 11 12
68 48 74 18 56
9 10 11 12
68 48 26 18 56
8 9 10 11 12 stop
Construct Heap (or Heapify)
▪ One application of heaps is sorting. But how do we start a heap first? ▪ Problem: Given array A[1..n], rearrange its items to form a heap.
▪ Solution 1: Sort A[1..n] in descending order. Yes, but that’s circular! ▪ Solution 2: Build Incrementally:
That is, make A[1..t] a max heap while incrementing t 1 .. n.
That is, for t 1 .. n do
UpHeap(A, t) end
Time=Qh i2i i=0
= Q(n log n)
Most nodes are concentrated near the bottom with larger depths but smaller heights. Idea: DownHeap is better!
Heap Construction Algorithm
Solution 3: Build Backwards on t by DownHeap(A,t).
Assume items in nodes 1..t-1 are tentatively + so that DownHeap’s Pre-Cond is met.
procedure ConstructHeap(A[1..n]) § O(n) time Pre-Cond: input is array A[1..n] of arbitrary numbers Post-Cond: A is rearranged into a max-heap
size[A] n § establish last node barrier LastNonleafNode n/2
for t LastNonleafNode downto 1 do DownHeap(A, t)
h1 Time=Q(h−i)2i
= Qj2h−j j=0 h
T(|L|) + T(|R|) + O(log n)
T(n) = O(n)
= 2h Q( j2− j ) j=0
= 2h Q(1) = Q(n)
Construct Heap Example
51 62 12 92
Construct Heap Example
3 DownHeap(A,t) 42 t=6
51 62 12 92
Construct Heap Example
3 DownHeap(A,t) 42 t=5
51 62 56 92
Construct Heap Example
3 DownHeap(A,t) 42 t=4
51 88 56 92
Construct Heap Example
3 DownHeap(A,t) 42 t=3
94 88 56 92
Construct Heap Example
3 DownHeap(A,t) 92 t=2
94 88 56 42
Construct Heap Example
DownHeap(A,t) t=1
Construct Heap Example
83 62 56 42
Heap as a Priority Queue
A Priority Queue (usually implemented with some “heap” structure)
is an abstract Data Structure that maintains a set S of items and supports the following operations on it:
MakeEmptyHeap(S): Make an empty priory queue and call it S.
ConstructHeap(S): Insert(x, S): DeleteMax(S):
Construct a priority queue containing the set S of items. Insert new item x into S (duplicate values allowed) Remove and return the maximum item from S.
Note: Min-Heap is used if we intend to do DeleteMin instead of DeleteMax.
Priority Queue Operations
Array A as a binary heap is a suitable implementation.
For a heap of size n, it has the following time complexities:
O(1) O(n) O(log n)
MakeEmptyHeap(A) ConstructHeap(A[1..n]) Insert(x,A) and DeleteMax(A)
size[A] 0 discussed already see below
procedure Insert(x,A)
size[A] size[A] + 1 A[ size[A] ] x UpHeap(A, size[A] )
procedure DeleteMax(A)
if size[A] = 0 then return error
MaxItem A[1] A[1] A[size[A]]
size[A] size[A] – 1 DownHeap(A, 1) return MaxItem
A word on Priority Queues
• In many priority queue applications, an item and the priority of the item are two distinct object types.
• For instance: items are vertices in a graph, while priority of an item is the shortest distance from source to the corresponding vertex in the graph.
• We store (pointers to) items in the nodes of the heap, while item priorities are stored separately, external to the heap.
• We also maintain two-way “pointers” (node[v] and v) between items and their heap node location for direct access both ways. (node[v]=0 means v is not in the heap.)
• Heap ordering property is based not on the items but their priorities.
• The result is a priority adaptable location aware priority queue.
priority d[v]
node[v] = t
Algorithm HeapSort(A[1..n]) § O(n log n) time Pre-Cond: input is array A[1..n] of arbitrary numbers
Post-Cond: A is rearranged into sorted order
ConstructMaxHeap(A[1..n]) for tn downto 2do
A[t] DeleteMax(A) end
HeapSort Example
(pages 36 – 68)
1 2 3 4 5 6 7 8 9 10 11 12
already constructed
94 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 56 heap swap
68 48 74 18 56
8 9 10 11 12
size[A] = 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18 | 94
68 48 74 18 94 8 9 10 11 12
size[A] = 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 82 | 92 | 74 | 76 | 68 | 88 | 68 | 48 | 74 | 18
DownHeap(A,1)
68 48 74 18 94 8 9 10 11 12
size[A] = 11
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
92 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 18
size[A] = 11
68 48 74 18 94 8 9 10 11 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92
68 48 74 92 94 8 9 10 11 12
size[A] = 11
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 82 | 88 | 74 | 76 | 68 | 56 | 68 | 48 | 74 | 92 | 94
DownHeap(A,1)
68 48 74 92 94 8 9 10 11 12
size[A] = 10
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
88 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 74 |
size[A] = 10
68 48 74 92 94 8 9 10 11 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 |
68 48 88 92 94 8 9 10 11 12
size[A] = 10
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 82 | 68 | 74 | 76 | 18 | 56 | 68 | 48 | 88 | 92 | 94
DownHeap(A,1)
68 48 88 92 94 8 9 10 11 12
size[A] =9
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
82 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 48 |
88 | 92 | 94
size[A] =9
68 48 88 92 94 8 9 10 11 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 |
88 | 92 | 94
68 82 88 92 94 8 9 10 11 12
size[A] =9
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 76 | 68 | 74 | 74 | 18 | 56 | 68 | 82 | 88 | 92 | 94
DownHeap(A,1)
68 82 88 92 94 8 9 10 11 12
size[A] =8
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
76 | 74 | 68 | 68 | 74 | 18 | 56 | 48 |
82 | 88 | 92 | 94
size[A] =8
48 82 88 92 94 8 9 10 11 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 74 | 68 | 68 | 74 | 18 | 56 | 76 |
82 | 88 | 92 | 94
76 82 88 92 94 8 9 10 11 12
size[A] =8
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 74 | 68 | 68 | 74 | 18 | 56 |
76 | 82 | 88 | 92 | 94
DownHeap(A,1)
76 82 88 92 94 8 9 10 11 12
size[A] =7
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 74 | 68 | 68 | 48 | 18 | 56 |
76 | 82 | 88 | 92 | 94
size[A] =7
76 82 88 92 94 8 9 10 11 12
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 74 | 68 | 68 | 48 | 18 | 74 |
76 | 82 | 88 | 92 | 94
76 82 88 92 94 8 9 10 11 12
size[A] =7
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 74 | 68 | 68 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94
DownHeap(A,1)
76 82 88 92 94 8 9 10 11 12
size[A] =6
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
74 | 68 | 68 | 56 | 48 | 18 | 74 | 76 | 82 | 88 | 92 | 94 swap
18 74 8 9 10 11 12
size[A] =6
76 82 88 92 94
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 68 | 68 | 56 | 48 | 74 |
74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =6
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 68 | 68 | 56 | 48 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =5
DownHeap(A,1)
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
68 | 56 | 68 | 18 | 48 | 74 | 74 | 76 | 82 | 88 | 92 | 94 swap
76 82 88 92 94
8 9 10 11 12
size[A] =5
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 56 | 68 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =5
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 56 | 68 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =4
DownHeap(A,1)
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
68 | 56 | 48 | 18 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94 swap
76 82 88 92 94
8 9 10 11 12
size[A] =4
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 56 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =4
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 56 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =3
DownHeap(A,1)
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 18 | 48 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =3
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =3
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =2
DownHeap(A,1)
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
48 | 18 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =2
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
76 82 88 92 94
8 9 10 11 12
size[A] =2
HeapSort Example
1 2 3 4 5 6 7 8 9 10 11 12
18 | 48 | 56 | 68 | 68 | 74 | 74 | 76 | 82 | 88 | 92 | 94
size[A] =1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com