[理工] [資結]-sort

[polomoss (小澤)]

請問一下，當資料量很大的時候


排序速率: Quicksort > Mergesort > Heapsort



是為什麼?  是由程式run出來的結果，還是有定理或什麼可以證明


題目問why，不知道怎麼解釋

--
┌這篇文章讓您覺得？─────────────────────────────┐
│                                                                            │
│    一"一     \  /    >\\\<    ╯ ╰    ∩ ∩    ▁ ▁   ＞＿＜    ㄧ ㄧ+   │
│      皿               ε       □        ▽    ▇Δ ▇   ╰╯        ╯    │
│     北七     亂喔     害羞     莎笅     爽啦     哭爸     ＸＤ     科科    │
└──────────────────────────────────────┘

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.14.2
推 FRAXIS:定理的話 已經有人證明這三種sort在averge case情況下
→ FRAXIS:的複雜度 包含係數都可以算出來
→ polomoss:所以除非知道定理，不然考試沒辦法證明出來是吧~?
→ NOtWorThy:跟計組第7章有關係
推 FRAXIS:我覺得他只是要你申論吧 看這三種演算法到底是快在哪..
→ FRAXIS:像Heapsort就說他還要維持一個heap的形狀 實做比較複雜 慢
→ FRAXIS:Mergesort要一個額外陣列搬來搬去 所以比不上quicksort
→ doom8199:怎麼怪怪的... Quicksort 應該是三者裡面最慢的
推 eddie780217:樓上  Qiucksort在Average case下的確是最快的
→ eddie780217:打錯  是Quicksort才對= =
→ doom8199:但它的 worst case 並非 O(nlogn)
→ doom8199:對程式的穩定性來說， Mergesort 和 Heapsort 再怎麼糟
→ doom8199:也只會到 O(nlogn) .Quicksort 快在有可能比 O(nlogn)
→ doom8199:還小，但只對特定情況才會如此
推 eddie780217:是指"Average case"的情況下 Quicksort才最快
→ doom8199:恩，我知道， 只是我覺得實用性應該要倒過來 OTZ
→ converse2006:其實聖經本上面有平均時間的數據 Quick sort穩穩領先
→ ssccg:Average case下快為什麼實用性要倒過來
→ ssccg:程式的穩定性也不是用worst case當唯一指標吧
→ ssccg:Quicksort並不是快在有可能比O(nlogn)小，而是在大部分case
→ ssccg:比另外兩者快常數/低order的時間
→ ssccg:注意是大部分，反而應該說在特定情況才會比較慢