作者Nt1 (用功點吧!)
看板CSSE
標題[問題] 請教 exchange sort 演算法
時間Wed Mar 1 20:37:53 2006
我是一個要準備考試的考生,在看老師的講義時有看到 exchange sort 演算法,是屬於
stable 的演算法,但是我實際用手算了好多次,發現怎麼算都是 unstable …
請問一下,是我哪邊算錯了,還是 exchange sort 就是 unstable 的排序演算法呢?
code:
exchange_sort()
{
for (inti=0;i<size;i++){
for (int j=i+1,j<size;j++){
if(a[i]>a[j]) then swap(a[i],a[j]);
}
}
}
/*
一開始 a[0]和a[1]比,如果a[0]>a[1],則互換,接著a[0]和a[2]比...
直到a[0]和a[n]比完。
再來a[1]和a[2]比……一直比到a[n-1]
*/
4,2,5,8,8+,6 (原始資料)
2,4,5,8,8+,6 (4>2,互換)
2,4,5,6,8+,8 (8>6,互換)
排完後,8 和 8+ 的位置不一樣了,請問…這樣不是應該是 unstable 嗎?
可是我們老師的講義上寫 stable ,後面列的表格也是 satble,覺得很疑惑 @@
google 和學校圖書館都沒什麼關於 exchange sort 的資料,我也知道它不重要…只是
一直有個疙瘩在心中~~~書都念不下去了~~請各位指正一下!是我關念有錯還是講義寫錯
謝謝!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.135.113.45
推 hardcover:exchange sort(bubble sort): stable 03/01 22:50
→ hardcover:selection sort: unstable 03/01 22:51
→ hardcover:應該是這樣 XD 03/01 22:51
推 edwar:(a[i]>a[j]) 改成 >= 呢? 03/01 23:22