CS61B Lectures #28
• Selection sorts, heap sort • Merge sorts
• Quicksort
Readings: Today: DS(IJ), Chapter 8; Next topic: Chapter 9.
Copyright By PowCoder代写 加微信 powcoder
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 1
Sorting by Selection: Heapsort
Idea: Keep selecting smallest (or largest) element.
• Really bad idea on a simple list or vector.
• But we’ve already seen it in action: use heap.
• Gives O(N lg N ) algorithm (N remove-first operations).
• Since we remove items from end of heap, we can use that area to accumulate result:
original: heapified:
Sorted part
19 0 -1 7 23 2 42
42 23 19 7 0 2 -1 23 7 19 -1 0 2 42 1972-10 2342 7 0 2 -1 19 23 42 20-1 7192342 0-1 27192342 -1 027192342 -1 0 2 7 19 23 42
Last modified: Fri Apr 3 16:08:34 2020
CS61B: Lectures #28 2
Sorting By Selection: Initial Heapifying
• When covering heaps before, we created them by insertion in an initially empty heap.
• When given an array of unheaped data to start with, there is a faster procedure (assume heap indexed from 0): [corrected 4/3]
void heapify(int[] arr) {
int N = arr.length; for(intk=N/2;k>=0;k-=1) {
for(intp=k,c=0;2*p+1
• Repeat recursively on the high and low pieces.
• For speed, stop when pieces are “small enough” and do insertion sort
on the whole thing.
• Reason: insertion sort has low constant factors. By design, no item will move out of its piece [why?], so when pieces are small, #inver- sions is, too.
• Have to choose pivot well. E.g.: median of first, last and middle items of sequence.
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 7
Example of Quicksort
• In this example, we continue until pieces are size ≤ 4.
• Pivots for next step are starred. Arrange to move pivot to dividing
line each time.
• Last step is insertion sort.
• Now everything is “close to” right, so just do insertion sort:
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 8
Performance of Quicksort
• Probabalistic time:
– If choice of pivots good, divide data in two each time: Θ(N lg N )
with a good constant factor relative to merge or heap sort.
– If choice of pivots bad, most items on one side each time: Θ(N2).
– Ω(N lg N ) in best case, so insertion sort better for nearly or- dered input sets.
• Interesting point: randomly shuffling the data before sorting makes Ω(N2) time very unlikely!
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 9
Quick Selection
The Selection Problem: for given k, find kth smallest element in data.
• Obvious method: sort, select element #k, time Θ(N lg N ). • If k ≤ some constant, can easily do in Θ(N) time:
– Go through array, keep smallest k items.
• Get probably Θ(N) time for all k by adapting quicksort:
– Partition around some pivot, p, as in quicksort, arrange that pivot ends up at dividing line.
– Suppose that in the result, pivot is at index m, all elements ≤ pivot have indicies ≤ m.
– If m = k, you’re done: p is answer.
– If m > k, recursively select kth from left half of sequence.
– If m < k, recursively select (k − m − 1)th from right half of sequence.
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 10
Selection Example
Problem: Find just item #10 in the sorted version of array:
Initial contents:
51 60 21 -4 37 4 49 10 40* 59 0 13 2 39 11 46 31 0
Looking for #10 to left of pivot 40:
13 31 21 -4 37 4* 11 10 39 2 0 40 59 51 49 46 60
Looking for #6 to right of pivot 4:
-4 0 2 4 37 13 11 10 39 21 31* 40 59 51 49 46 60 4
Looking for #1 to right of pivot 31:
-4 0 2 4 21 13 11 10 31 39 37 40 59 51 49 46 60
Just two elements; just sort and return #1:
-4 0 2 4 21 13 11 10 31 37 39 40 59 51 49 46 60
Result: 39
Last modified: Fri Apr 3 16:08:34 2020
CS61B: Lectures #28 11
Selection Performance
• For this algorithm, if m roughly in middle each time, cost is
C ( N ) = 1 , i f N = 1 , N + C(N/2), otherwise.
= N+N/2+...+1 = 2N−1∈Θ(N)
• But in worst case, get Θ(N2), as for quicksort.
• By another, non-obvious algorithm, can get Θ(N) worst-case time
for all k (take CS170).
Last modified: Fri Apr 3 16:08:34 2020 CS61B: Lectures #28 12
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com