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.

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

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:

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!