[理工] [DS] 96成大資工

[jameschou (DOG)]

http://ppt.cc/;S0T

DS的最後一題(第4題)

我的感覺是覺得應該是(a)要找個圖去對,(b)要找個圖去對.. 等等
但是我手邊有的參考答案是每個Fig去對一種sort 而且還冒出一個bubble sort


所以想要討論一下答案 希望有人能提供一下想法

a) merge sort -> Fig.1
b) insertion sort -> Fig.2
c) heap sort -> ??? (我想寫Fig.4)
d) quick sort -> Fig.3
e) selection sort -> ??? (我還是想寫Fig.4)


(c)(e)希望有人可以幫忙解答一下@@


至於第六個圖我是用很簡單的O(n^2)的方法去依序找最大值
因為題目似乎沒有其他規定(不過我手邊的答案是用heap sort,我覺得有點麻煩,code太長)
用C語言會有點類似這樣:

//設有n個元素,存在A[1]~A[n]中

for(int i=n;i>=1;i--){
    k = i;
    for(int j=i-1;j>=1;j--)
        if(A[j]>A[k])
            k=j;
    swap(A[i],A[k])        //或者也可以更詳細寫出int t=A[i];A[i]=A[k];A[k]=t;
}


不知道有沒有人能提供一些看法
先謝謝大家了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.167.75.142
推 tureday:heap sort是Fig.6  selection sort是Fig.4
→ tureday:heap sort最大先排好，剩餘資料較鬆散，選擇排序挑小的，
→ tureday:每經過一個pass比較次數會越來越少
→ dy957:高銘課本解答給fig.5 heap sort fig.6 bubble = ="
→ skyevolution:可以去wiki查這些sort 網頁右手邊就有這些圖
→ dy957:那fig.6應該是heap sort沒錯
→ jameschou:sky大的資訊真是太有用了!! wiki上的gif超酷XD
→ jameschou:如果看wiki上的 fig.6的確是heap沒錯 fig.5是bubble
→ jameschou:但我這個類似把selection sort先取小的改成先取大的
→ jameschou:來跑應該也會產生類似fig.6的圖 因為其實只是把fig.4倒
→ jameschou:過來而已   只是不知道這樣會不會算分..
推 KOFXI:感謝sky大的說明...不過好久才看到