[理工] [資結]-Quicksort

看板Grad-ProbAsk作者 (...)時間16年前 (2010/03/02 02:29), 編輯推噓6(6推 0噓 21→)
留言27則, 3人參與, 最新討論串1/1
請問Quicksort在全部的input的key值都相等時 會發生什麼情形呢 ? //partition的作法 pivot=list[m].key; repeat repeat i++; until list[i].key>=pivot repeat j--; until list[j].key<=pivot if(i<j)swap(list[i],list[j]); until(i>=j) swap(list[m],list[j]);//pivot就定位 以上這段code 在全部的element key值都相等時 每次partition還是會把pivot放到中間吧 ? 所以應該算是成功的分割 ? 可是看考題好像說equal key很多的時候也會變成worst case 請問是為什麼呢 ? 還有要怎樣解決 @@ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.126.125.176 ※ 編輯: EntHeEnd 來自: 59.126.125.176 (03/02 02:30)
推
03/02 02:34, , 1F
根據我驚人的判斷力
03/02 02:34, 1F
→
03/02 02:34, , 2F
1. 程式中應該是J--
03/02 02:34, 2F
→
03/02 02:36, , 3F
2. key值都相等就像sort好一樣 pivot不會在中間
03/02 02:36, 3F
→
03/02 02:36, , 4F
3. 解法很有可能是先統計equal key 重複個數
03/02 02:36, 4F
→
03/02 02:37, , 5F
然後把他視為只有一個 sort完在插回去
03/02 02:37, 5F
→
03/02 02:38, , 6F
對 我打錯了XD
03/02 02:38, 6F
※ 編輯: EntHeEnd 來自: 59.126.125.176 (03/02 02:38)
→
03/02 02:39, , 7F
請問為什麼不會在中間 ?
03/02 02:39, 7F
→
03/02 02:39, , 8F
裡面的repeat迴圈還是會執行到i,j交錯不是嗎 ?
03/02 02:39, 8F
推
03/02 02:40, , 9F
哎呀 很有可能是 你又打錯了 程式碼應該是沒有等號
03/02 02:40, 9F
→
03/02 02:40, , 10F
ij交錯之後 出迴圈 就會把pivot和現在的j交換 @@
03/02 02:40, 10F
→
03/02 02:40, , 11F
03/02 02:40, 11F
→
03/02 02:41, , 12F
程式碼有等號...
03/02 02:41, 12F
→
03/02 02:41, , 13F
就算沒等號 他還是會做到i,j交錯才出迴圈阿
03/02 02:41, 13F
→
03/02 02:42, , 14F
裡面的repeat 每次加一次就結束 但是外層的repeat會讓他
03/02 02:42, 14F
→
03/02 02:42, , 15F
做到i j 交錯阿
03/02 02:42, 15F
推
03/02 02:43, , 16F
真的有耶 完了
03/02 02:43, 16F
→
03/02 02:44, , 17F
可是我看考題的考法 好像說這樣也會是worst case ?
03/02 02:44, 17F
→
03/02 02:48, , 18F
清大和成大好像都問過Quicksort遇到很多equal key的時候
03/02 02:48, 18F
→
03/02 02:48, , 19F
會怎樣 要怎樣解決的問題...
03/02 02:48, 19F
→
03/02 02:52, , 20F
我剛剛翻algo課本 好像有另外一種partition的方法...
03/02 02:52, 20F
→
03/02 02:53, , 21F
好像的確會造成無效切割 可是考試又不知道是哪一種分割法
03/02 02:53, 21F
推
03/02 03:04, , 22F
請教一下，那如果Q-sort有相同key，複雜度是多少呢?
03/02 03:04, 22F
→
03/02 03:06, , 23F
如果是我上面列的這種partition感覺和Best case一樣...
03/02 03:06, 23F
→
03/02 03:07, , 24F
如果是Algo課本上的partition 就是和sorted input的一樣
03/02 03:07, 24F
推
03/02 03:10, , 25F
sorted input複雜度是??
03/02 03:10, 25F
→
03/02 03:10, , 26F
就是worst case O(n^2)
03/02 03:10, 26F
推
03/02 03:22, , 27F
嗯，謝謝^^
03/02 03:22, 27F
‣ 更多 EntHeEnd 的文章
文章代碼(AID): #1BZ0UAmp (Grad-ProbAsk)