[理工] [資結] 102交大資演 第9題

[kurc (辛拉麵)]

題目如下:

http://i.imgur.com/gfkrFsm.png

http://i.imgur.com/X33UFng.png

一開始看以為是quicksort

但是下去追蹤後完全不是這一回事

整個都沒排序到的感覺Orz

我自己做的部分: (這部分是錯的，因為沒注意到第二個else if沒i++的結果)

第一次partiton，pivot是4，結束後 1 0 0 1 4 2 3 1 0 2
                                ↑         ↑
                              low(值為-1)  high(指向data[5])



補充正解（感謝galapous大提醒盲點）

第一次 parition 後：4 1 3 2 0 1 0 0 1 2 low=-1 high=1

第二次：　　　　　　　3 2 2 1 1 1 0 0 0 low=1  high=6

第三次：　　　　　　　3 2 　　　　　　　low=0  high=2

第四次：　　　　　　　　　　　　　0 0 0 low=-1 high=3　

final content : 4 3 2 2 1 1 1 0 0 0 (Ans(1))

partition invoked: 4次　(Ans(2))

這個是由大排到小的quick sort:　最差時間複雜度　size^2 (Ans(3))

附上昨天怒打的驗證ＸＤ　http://goo.gl/ePgIJ0

給大家參考囉，如果有問題可以再討論

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.7.202
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422422380.A.AEC.html
推 APE36: pivot取中間值後就開始sort，
→ APE36: 比較好奇是(3)是否也是同樣Quick的Worst Case
推 galapous: 是quick sort吧，細節有點不同但原理一樣，會覺得怪應
→ galapous: 該是因為第一次選到的是worst case
推 galapous: 第一次做完4應該在第一個哦，注意他for loop中有個case
→ galapous:  i不會變
→ kurc: 喔喔感謝G大! 整個突破盲點! 我完全沒發現第二個if沒有++i
→ kurc: 這樣就是標準的quick sort沒錯，感恩～
推 AgentSkye56: 還是看不懂QQ"有人大大會詳細的做法嗎~~
推 galapous: trace code你會發現他把比pivot大的擺在pivot左邊小的放
→ galapous: 右邊
推 killerw74: 想問大家 這題第二題寫多少...
推 galapous: 5
※ 編輯: kurc (1.164.7.202), 01/29/2015 21:32:34