2019独角兽企业重金招聘Python工程师标准>>> 
Lecture 5
How fast can we sort?
comparison sorts
e.g. quicksort, insertion sort, merge sort, heapsort
No comparison sorting algorithm could run better than nlgn.
====================================
Decision-tree modal (binary tree)
A decision tree can model the execution of any comparison sort:
=> One tree for each input size n
=> View the algorith as splitting whenever it compares two elements
=> tree lists comparsions along all possible instruction traces
=> running time (# comparsisons) = length of path
worst case running time = the height of the tree (the longest path)
Lower bounder on decision tree sorting:
Any decision tree sorting n elements must have height omaga(nlgn)
====================================
Sorting in linear time
====================================
Counting sort
input: A[1:n], each A[i] belongs to {1, 2, 3, ..., k}
output: B[1:n] = sorting of A
Auxiliary storage c[1 ... k]
for i <- 1 to k
do c[i] <- 0
for j <- 1 to n
do c[a[j]] <- c[a[j]] + 1 //c[i] is the total number of elements whose value equal to i
for j <- 2 to n
do c[j] = c[j-1] + c[j] //c[j] is the total number of elements whose value <= j
for j <- n downto 1
do B[c[a[j]]] <- A[j] //where A[j] should go in B
c[a[j]] <- c[a[j]] - 1
running time = zita(k) + zita(n) + zita(k) + zita(n) = zita(n+k)
if k = zita(n) ==> linear time sorting algorithm
if k is relatively small -> good sorting algorithm
===================================
stable sort perserve the relative order of equal elements
counting sort is a stable sort
===================================
Radix sort
digit by digit sort
least sig -> most sig (must be stable sort)
use counting sort as a subroutine
---- use counting sort for each digit (k+n)
---- say n integer, each b bits
---- split each integer b/r digits, each r bits long
