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

• 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