Re: [理工] [資結]-sort

[NOtWorThy ()]

※ 引述《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
推 tryPTT:答案一定的喔 你可以用幾個數字(包含相同key)代一下就知了
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.218.120
推 tryPTT:如果你改成=就會變unstable沒錯，不過這樣就變多此一舉了。
→ NOtWorThy:那考試出來是要怎麼辦阿= =  誰知她演算法怎寫?!
推 converse2006:請翻聖經本 裡面自然會跟你說為什麼
→ converse2006:看不懂英文就直接看CODE C的版本很好懂
推 tsarnfeng:你的想法沒錯 但是 規則是人訂的我們只是遵從的人
→ tsarnfeng:不是創始者
→ ssccg:可以寫成stable的就是stable，不能的才會說是unstable
推 polomoss:能有更好的演算法可以是stable，為何硬要寫成unstable
→ polomoss:而那些unstable是沒辦法改盡到stable才稱unstable