Sorting Algorithms Summary

Sorting Algorithms Summary


Comparison-based Sorting: 4
Decision Tree Model: for study the limit of comparison-based sorting
Prove: The lower bound of running time for any c-based sorting algorithm is nlogn
--> omega(nlogn), both of Heap Sort and Merge Sort are almost the best of them.

1. Insertion sort:
worst case theta(n^2)
suitable for the small size of input data
in-place sorting: 除待排序数组本身，仅有常数个元素需要存储

2. Merge sort:
theta(nlogn)
non-in-place sorting

3. Heap sort:
O(nlogn) in-place sorting

4. Quicksort:
in-place sorting worst case theta(n^2)
expected running time theta(nlogn)
in the real situation, it is faster than Heap Sort
与insertion sort类似，二者code紧凑，运行时间隐含常数系数很小
Suitable for the Large size of input data

Non-Comparison-based Sorting 
--it may break the lower bound of nlogn.
1. 计数排序
Counting Sort
假定输入元素值均在集合{0，1，2，..., k}内，用数组索引作为确定相对次序的工具
running time: theta(k+n)
k = O(n), linear time

2. 基数排序
Radix Sort
扩展计数排序的适用范围
n个整数，每个整数d位数字，每个数字可能值k个，基数排序在theta(d(n+k))完成
d = constant, k = O(n), linear time

3. Bucket Sort
需要了解输入数组的概率分布，对半开区间 [0,1)服从均匀分布的n个实数，平均情况O(n)

Algorithms      Worst Case      Average Case/ Expected Running time
Insertion           theta(n^2)                theta(n^2)
Merge               theta(nlogn)             theta(nlogn)
Heap                 O(nlogn)                  --
Quick                theta(n^2)                theta(nlogn)
Counting           theta(k+n)               theta(k+n)
Radix                theta(d(n+k))           theta(d(n+k))
Bucket              theta(n^2)                 theta(n)



评论

发表评论

此博客中的热门博文

8 Link Analysis

图片
Pagerank—link analysis  Early web search: extract keywords-->queries match -->page ranked by  occurrences of keywords Term Spam: (TS) Disguise a page as sth it is not about  Pagerank: vs TS Rank pages by linkage too How many pages point to a page= # incoming links => importance Link spam (fade incoming pointers) Manually identify some important pages and assign them page ranks , then let ranks propagate to other nodes. Random surfer model  Random surfer start from any page follow its outgoing links randomly   来，去，都是随机的 Pagerank = Prob ( a random surfer lands on the page ) More robust than manual approach , a collective voting scheme Limiting distribution  Graph is strongly connected , a node can reach any other node in the graph But cannot have dead end & spider traps A--->B, C, D;    B--->A, D,(A,D->C);     C--->A(->B,C,D);   ...
继续阅读

1 Map reduce problems

图片
PROBLEMS Join   Matrix multiplication 2 / 1 phase  Matrix vector multiplication  POINTS Map reduce input output Memory requirement  Reducer size  Communication cost P1 Join:  R ( A , B )  S ( A , C )   1. Map r ( a , b ) => ( a , ( 'R' , b ));  s ( a , c ) => ( a , ( 'S' , c ))   2. Reduce ( a , [( 'R' , b ), ( 'S' , c1 ), ( 'S' , c2 )]) => ( a , ( b , c1 )), ( a , ( b , c2 ))   Dangling tuples: Key with values from only 1 relation  ( a , [( 'R' , b )]) => left dangling ; ( a , [( 'S' , c )]) => right dangling  P2 Matrix-multiplication  C mXn = A mXp B pXn  2 phase: a. phase1  product  Map : Extract key from A ’ s c , B ’ s r A [ i , k ] => ( k , ( 'A' , i , A [ i , k ])) ; B [ k , j ] => ( k , ( 'B' , j , B [ k , j ]))   Communication cost : mp + np  Reduce...
继续阅读

NoSql and AWS DynamoDB practices

图片
no sql and dynamoDB https://mp.weixin.qq.com/sbiz=MzAxMzA2MDYxMw==&mid=2651560478&idx=1&sn=e8ce8d0ff0067059cf9946eee50bcbf6&chksm=80576574b720ec626102d9eca08da2424fedb3d0d58770cc26ed5ae8402a37ee97ae2c4441b1&mpshare=1&scene=24&srcid=0416hM7NzIQUooRU92fn4VOv&key=017ace5cd749d20d13db07527244da37a6c4e17bce708cfa37916f41f4f2cf0450b750489db9c37ee67227bbbd43207b03aaed62b9cea6e3d931a61a83e29b5ce94e014a496ea83f5effe88ca0c7d4f8&ascene=0&uin=ODc5NTM5MzAx&devicetype=iMac+MacBookPro13%2C2+OSX+OSX+10.12.3+build(16D32)&version=12020110&nettype=WIFI&fontScale=100&pass_ticket=TZiwhj6StjhSR05qVUyKEcClLlArTC5CqpFW3qEaROK%2FfI7ojwh9a1esoikANmQh Relational database: Mature and stable Feature rich versatile query language Acid  No sql  Flexible  Scaled out easily Data replicated over multi-servers Weak consistency high availability Scale up out Scale up vertical , CPU Scale out adding more computers ...
继续阅读