PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[轉錄][閑聊] 超越quickSort的sort是..?

看板Prob_Solve (計算數學 Problem Solving)作者 (痞子軍團團長)時間18年前 (2006/12/15 01:01), 編輯推噓14(14推 0噓 9→)
留言23則, 6人參與, 最新討論串1/2 (看更多)
※ [本文轉錄自 C_and_CPP 看板] 作者: XX9 () 看板: C_and_CPP 標題: [閑聊] 超越quickSort的sort是..? 時間: Wed Dec 13 23:15:49 2006 今天聽老師講到quick sort是近年最快的排序大法 不過這個記錄去年被打破了 請問一下 這個排序是...?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 210.64.100.15
推
12/14 01:10,
純演算法角度評論的話，很難超越它吧？
12/14 01:10
推
12/14 02:16,
排序法的效能最快也只能到O(NlogN) quick已經達到了
12/14 02:16
→
12/14 02:20,
所以就算有超越quickSort的SORT 也快不了多少的~
12/14 02:20
→
12/14 02:22,
我覺得quicksort的對手是Merge sort 跟 Heap sort吧XD
12/14 02:22
推
12/14 10:46,
應用comparison tree形式的sorting可以證明最優是 NlogN
12/14 10:46
→
12/14 10:47,
要打破的話就要用其他方法..前年看到一篇NloglogN的..@@"..
12/14 10:47
推
12/14 11:41,
NloglogN ? 應該有特定限制吧?
12/14 11:41
→
12/14 11:42,
一般來說, 混合式會是比較強力的
12/14 11:42
→
12/14 11:43,
用統計來看, 多少筆資料量以下的用 insertion, 多少以上用
12/14 11:43
→
12/14 11:43,
quicksort 這樣
12/14 11:43
→
12/14 11:44,
如果複雜度沒得改進, 那麼就要改常數
12/14 11:44
推
12/14 13:48,
comparison and swap的sort很難比quick sort好
12/14 13:48
推
12/14 16:47,
quickSort 最差複雜度不也是 n^2 嗎？？
12/14 16:47
→
12/14 16:47,
quickSort 的平均複雜度才是 NlogN ??
12/14 16:47
→
12/14 16:48,
值有範圍的話 counting sort 不是最快 N 嗎？ XD
12/14 16:48
推
12/14 17:01,
請問OOJ NloglogN的是哪一種演算法？
12/14 17:01
推
12/14 17:42,
counting sort 的限制除了值有範圍, 還要多用記憶體
12/14 17:42
→
12/14 17:42,
跟 quicksort 比不公平啦 Orz
12/14 17:42
-- 侃侃長論鮮窒礙 網站：http://www.psmonkey.idv.tw 眾目睽睽無心顫 個人版：telnet://legend.twbbs.org 煢居少聊常人事 殺頭容易告白難 歡迎參觀 Java 版（@ptt.cc）精華區 \囧/ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.192.56
推
12/15 09:30, , 1F
是有看到一篇 Deterministic Sorting in O(nloglogn) Time
12/15 09:30, 1F
→
12/15 09:30, , 2F
and Linear Space 的
12/15 09:30, 2F
→
12/15 09:30, , 3F
不過那是 integer sorting
12/15 09:30, 3F
推
12/16 18:37, , 4F
整數排序的話 好像早就有了 好像還有更好的
12/16 18:37, 4F
推
12/17 13:44, , 5F
丟到HashingTable中最快.只要O(n).以空間換取時間XD
12/17 13:44, 5F
推
12/18 02:03, , 6F
樓上丟進去後怎麼從小取到大? 問題還很多吧~?
12/18 02:03, 6F
推
12/18 17:39, , 7F
HashingTable建立時間O(n),搜尋時間O(1).沒有錯吧.
12/18 17:39, 7F
→
12/18 17:42, , 8F
從頭找到尾需要搜尋整區段的時間->O(n),結果最後還是O(n)
12/18 17:42, 8F
推
12/18 17:48, , 9F
修正一下.全部是 O(n+e)= O(n)
12/18 17:48, 9F
推
12/18 22:01, , 10F
不能這樣算呀, input size 的 n 跟 hash size 的 n 是不同的
12/18 22:01, 10F
→
12/18 22:02, , 11F
照你的 hash table 法, 不就每個可能的值都要有一格?
12/18 22:02, 11F
推
12/18 22:10, , 12F
這個本來就只算到n,就算再分解e=n+k,O(2n+k)結果還是O(n)
12/18 22:10, 12F
→
12/18 22:11, , 13F
一個值一格沒錯,所以我才說以空間換取時間呀XD
12/18 22:11, 13F
推
12/19 02:21, , 14F
可以講詳細點嗎? 好像跳太快... 看不出搜尋整段的 e 是啥
12/19 02:21, 14F
→
12/19 02:22, , 15F
舉個例子也許比較快?
12/19 02:22, 15F
推
12/19 17:49, , 16F
參考:依座號排序學生資料、點名程式...
12/19 17:49, 16F
→
12/19 17:49, , 17F
當n(資料筆數)>e(總位址數)會造成OverFlow,所以n必須<=e
12/19 17:49, 17F
→
12/19 17:50, , 18F
當n接近e時,k(未用位址)就會接近0,所以結果O(2n+k)=>O(n)
12/19 17:50, 18F
推
12/24 02:09, , 19F
嗯..我看的是ACM "Sorting in linear time?" 這一篇~
12/24 02:09, 19F
→
12/24 02:10, , 20F
要擺脫nlogn 就不能完全倚賴用比較的方式來完成sorting
12/24 02:10, 20F
推
01/20 01:24, , 21F
colawe到底在講什麼
01/20 01:24, 21F
推
01/22 18:58, , 22F
我只是想說.QSort並非在任何情況下都是最佳解.如此而已.
01/22 18:58, 22F
推
05/07 15:06, , 23F
quick sort 最棒!!!!!!
05/07 15:06, 23F
‣ 更多 PsMonkey 的文章
文章代碼(AID): #15WODZl- (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 PsMonkey 的文章
文章代碼(AID): #15WODZl- (Prob_Solve)