CS代考 CS61B Lectures #28 – cscodehelp代写

CS61B Lectures #28
• Selection sorts, heap sort • Merge sorts
• Quicksort
Readings: Today: DS(IJ), Chapter 8; Next topic: Chapter 9.

Copyright By cscodehelp代写 加微信 cscodehelp

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 a pivot value at the high end of the sequence to be sorted, and everything ≤ on the low end.
• 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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com