作者yauhh (喲)
看板Prob_Solve
標題Re: [問題] 想要請教Shear sort
時間Mon Jun 1 19:58:14 2009
※ 引述《sakurarain (茫然不知所以)》之銘言：
: 不知道是不是有誰可以跟我大略講解一下這是個怎樣的演算法?
: 像是這個sort是如何做到的?時間複雜度那些方面的
: 或是有中文的網頁可以提供來讓小女子慢慢去研究就更好了
看了一點點,大意是說
要排 n 筆資料,是把資料排列成 n^(0.5) * n^(0.5) 方陣,
然後做 k 次以下步驟,據說這個 k 可以是 log_2 n + 1.
這 k 次分成單數次和偶數次,單數次將奇數列從右向左排序,將偶數列從左向右排序.
偶數次將每一行從上向下排序.
然後,時間複雜度起碼是從 n^(0.5) 算起,而不是從 n 算起了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.113.142
1F：推 seanwu:它是因為可以平行計算所以才能有n^0.5的吧? 06/01 23:50
2F：→ yauhh:意思是說,也許總共用2*n^(0.5)個node處理排序工作嗎? 06/02 00:22
3F：→ yauhh:其中n^(0.5)處理列的排序,另外n^(0.5)處理行的排序 06/02 00:23
4F：→ yauhh:突然想到,沒有人用機器架構在算複雜度的,是不是呢? 06/02 00:51
6F：→ deepdish:Shell 排序法 - 改良的插入排序 06/02 04:06
7F：→ yauhh:雖然頭韻很像,不一樣的東西就是不一樣,台科大跟台大差在哪裏 06/02 07:11
8F：推 seanwu:呃...如果能不作平行運算的話，那這個依照這個sort的原始 06/02 09:04
9F：→ seanwu:定義，它會是O(N^1.5 logN)的 06/02 09:06
10F：→ seanwu:其中對於每個行列的排序，之所以可以是O(N^0.5)的 06/02 09:07
11F：→ seanwu:是因為用了平行的奇偶交換排序,不然一般最好的是N^0.5logN 06/02 09:07
12F：→ seanwu:另外每行每列的排序若不能同時進行,總共就會多乘上O(N^0.5) 06/02 09:09
13F：→ seanwu:再說，即使排成N^0.5大的方陣，總資料量還是N的 06/02 09:10
14F：→ seanwu:儘從這裡是沒有辦法推定這個算法的複雜度的 06/02 09:10
15F：→ seanwu:(第一行錯字: 不能) 06/02 09:11
16F：→ seanwu:(n^(0.5))^3 log (n^0.5)^2，也是從 n^(0.5)算起的啊XD 06/02 09:13
17F：推 seanwu:五樓的板友，這個不是shell 06/02 09:16
18F：推 sakurarain:那個 感謝你告訴我解答 努力研究中~"~ 但是沒啥天份的 06/04 02:15
19F：→ sakurarain:說 還有如果要K過一遍英文才叫認真的話 那當我不認真 06/04 02:16
20F：→ sakurarain:吧>"< 我對英文有恐懼 更有跨不過的障礙啊!!Q口Q 06/04 02:16
21F：推 ledia:跨不過英文的障礙... 其實資訊學門也不好待了 ^^| 06/05 11:49