Google Search Box

自訂搜尋

Tuesday, May 11, 2010

[課業] 跟大家請教radix sort使用MSD的演算法

作者: chenyuchen (chenyuchen) 看板: Examination
標題: [課業] 跟大家請教radix sort使用MSD的演算法
時間: Tue May 11 21:59:16 2010

有關於radix sort的LSD和MSD
LSD:由最右邊的位數開始,由右往左
MSD:由最左邊的位數開始,由左往右

假設現在一個input array(12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18)
要使用radix sort來進行排序
當中使用LSD沒問題,可正常產生出排序好的結果
但如果使用MSD,以下為過程步驟

十位數
bucket content
0 2, 8, 4, 6
1 12, 16, 10, 18
2 28, 20,
3 30 ====>(2, 8, 4, 6, 12, 16, 10, 18, 28, 20, 30)
4
5
6
7
8
9

個位數
bucket content
0 10, 20, 30
1
2 2, 12
3 ====>(10, 20, 30, 2, 12, 4, 6, 16, 8, 18, 28)
4 4
5
6 6, 16
7
8 8, 18, 28
9
radix使用MSD演算法到此結束,但推出來的結果,卻不是排好序的array
請問一下是哪個地方我的推導過程出錯了?
(參考了王致強還有資料結構的聖經本,都只對LSD有詳細的範例,但卻沒有針對MSD有詳細的範例...)

1.考試科目:資料結構


2.章節名稱or篇名(單元關鍵字):CH7 Sorting


3.目前參考用書or考古題出處:高考資料結構-王致強、
Fundamentals of Data Structures in C


4.想問的內容:如上


5.想法:如上







1 comment:

  1. 推 dadan:從十位往個位排的時候弄錯了 是對各個bucket再sort 05/11 22:45
    → sgacy:違反版規關於課業文標題規定 請改正 05/11 22:54

    ReplyDelete