Lecture 32: Sorting I

CS61B

The Sorting Problem

Definition

An alternative point of view

Performance definitions

不是很懂这里的“extra"是什么意思

Selection Sort, Heapsort

Selection Sort

Heapsort

Naive Heapsort

Demo

Runtime Analysis

In-place Heapsort

In-place Heapsort

In-place Heapsort Runtime

Memory complexity

这里的Space complexity means auxiliary space complexity.

见讨论

Why does heap sort have a space complexity of O(1)?

Runtime上还是有很多不懂的！

Mergesort

Runtime analysis Demo
Mergesort demo

Runtime

So far

Insertion Sort

老师说很像你打扑克的时候，每摸到一张牌，自己会按照顺序插到已经拿到的牌里边儿，其实就是一个insertion sort的过程。

Naive approach

从Input里面一个元素一个元素地插入到新的output array里面：
Demo

In-place insertion sort:

Do everything in place using swapping

Demo

Number of swaps

Runtime

best case: 如果array是already sorted, 也就是绿色的字母是对角线，那么没有需要swap的，只需要N次compares,runtime是Θ（N）;
worst case: 如果每一个字母都需要从当前位置swap到第一位，也就是绿色的字母全部是每一行的第一列，那就相当于所有字母swap过的范围构成了一个等腰三角形，runtime是Θ（N^2）

pick the right sorting method

Insertion sorting is extremely fast on arrays with a small number of inversions

Sorts so far

Shell’s Sort (Extra)