Re: [問題] 想要請教Shear sort

[yauhh (喲)]

※ 引述《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
推 seanwu:它是因為可以平行計算所以才能有n^0.5的吧?
→ yauhh:意思是說,也許總共用2*n^(0.5)個node處理排序工作嗎?
→ yauhh:其中n^(0.5)處理列的排序,另外n^(0.5)處理行的排序
→ yauhh:突然想到,沒有人用機器架構在算複雜度的,是不是呢?
推 deepdish:http://0rz.tw/5NEMV
→ deepdish:Shell 排序法 - 改良的插入排序
→ yauhh:雖然頭韻很像,不一樣的東西就是不一樣,台科大跟台大差在哪裏
推 seanwu:呃...如果能不作平行運算的話，那這個依照這個sort的原始
→ seanwu:定義，它會是O(N^1.5 logN)的
→ seanwu:其中對於每個行列的排序，之所以可以是O(N^0.5)的
→ seanwu:是因為用了平行的奇偶交換排序,不然一般最好的是N^0.5logN
→ seanwu:另外每行每列的排序若不能同時進行,總共就會多乘上O(N^0.5)
→ seanwu:再說，即使排成N^0.5大的方陣，總資料量還是N的
→ seanwu:儘從這裡是沒有辦法推定這個算法的複雜度的
→ seanwu:(第一行錯字: 不能)
→ seanwu:(n^(0.5))^3 log (n^0.5)^2，也是從 n^(0.5)算起的啊XD
推 seanwu:五樓的板友，這個不是shell
推 sakurarain:那個 感謝你告訴我解答 努力研究中~"~ 但是沒啥天份的
→ sakurarain:說  還有如果要K過一遍英文才叫認真的話 那當我不認真
→ sakurarain:吧>"<  我對英文有恐懼 更有跨不過的障礙啊!!Q口Q
推 ledia:跨不過英文的障礙... 其實資訊學門也不好待了 ^^|