作者NOtWorThy ()
看板Grad-ProbAsk
標題Re: [理工] [資結]-sort
時間Wed Dec 16 00:03:15 2009
※ 引述《NOtWorThy ()》之銘言：
請問一下 為何Insertion sort是stable?
或者其他sort eq.bubble selection ...etc
我在想答案沒有一定吧?!
要是我在條件判斷式裡面把"<"改成"<="(or 反之)
就可能改變她是否stable 不是?!
因為這些都是在compare base底下
煩請高手 賜教
謝謝
ex. 我把判斷改成
while a[j]>=InsertData
a[j+1] <- a[j]
j <- j-1
(1 2 3 4 5 6 7 8 ) 5'
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
=> 1 2 3 4 5' 5 6 7 8
這樣不就變Unstable了??
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.218.120
1F：推 tryPTT:答案一定的喔 你可以用幾個數字(包含相同key)代一下就知了 12/15 23:53
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.218.120
2F：推 tryPTT:如果你改成=就會變unstable沒錯，不過這樣就變多此一舉了。 12/16 00:09
3F：→ NOtWorThy:那考試出來是要怎麼辦阿= = 誰知她演算法怎寫?! 12/16 00:14
4F：推 converse2006:請翻聖經本 裡面自然會跟你說為什麼 12/16 00:53
5F：→ converse2006:看不懂英文就直接看CODE C的版本很好懂 12/16 00:53
6F：推 tsarnfeng:你的想法沒錯 但是 規則是人訂的我們只是遵從的人 12/16 01:45
7F：→ tsarnfeng:不是創始者 12/16 01:45
8F：→ ssccg:可以寫成stable的就是stable，不能的才會說是unstable 12/16 05:51
9F：推 polomoss:能有更好的演算法可以是stable，為何硬要寫成unstable 12/16 11:02
10F：→ polomoss:而那些unstable是沒辦法改盡到stable才稱unstable 12/16 11:02