PTT數位生活區 / C_and_CPP (C/C++)

[問題] Merge Sort v.s. Quick Sort

看板C_and_CPP (C/C++)作者 (uu8nc)時間2年前 (2021/06/16 13:53), 2年前編輯推噓3(3推 0噓 9→)
留言12則, 8人參與, 2年前最新討論串1/1
大家好 小弟在測試merge sort 與 quick sor時發現 在一百萬筆long int的case下測試多次發現 merge sort的平均速度約為70ms 而quick sort的平均速度約為130ms 差了將近一倍 怎麼會這樣? 我是用隨機的亂數輸入陣列 而為了不要元素有那麼多重複的 我是用rand()*rand() 為甚麼quick sort會比merge sort慢了將近一倍@@ 這邊用的演算法都是最基礎的 沒有經過改良 還請各位大大幫我解惑了 查了許多資料都沒查到QQ 這是我的code https://ideone.com/Glm92N -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 116.241.212.216 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1623822807.A.444.html
→
06/16 13:59, 2年前 , 1F
是每次嗎？應該和選的 pivot 位置有關
06/16 13:59, 1F
→
06/16 14:06, 2年前 , 2F
樓上大大是每次沒錯，我的快排都是選v[0]當pivot
06/16 14:06, 2F
※ 編輯: MBS550L (116.241.212.216 臺灣), 06/16/2021 14:15:59
推
06/16 15:08, 2年前 , 3F
quick sort 在 pivot 選的最差的情況下是 O(n^2)
06/16 15:08, 3F
→
06/16 15:11, 2年前 , 4F
而 merge sort 是很穩定的 O(n*logn)
06/16 15:11, 4F
→
06/16 15:13, 2年前 , 5F
你有驗證過你寫的兩個sort的正確性了嗎?
06/16 15:13, 5F
推
06/16 15:51, 2年前 , 6F
第131、136行，陣列v好像都事先被第126行排序了.
06/16 15:51, 6F
→
06/16 18:15, 2年前 , 7F
各位不好意思= = 我m-sort的code有問題，不過無法自刪就
06/16 18:15, 7F
→
06/16 18:15, 2年前 , 8F
給大家當笑話看吧哈哈 debug之後q-sort是最快的沒錯...
06/16 18:15, 8F
→
06/16 19:21, 2年前 , 9F
有沒有quick sort不是最快的八卦XD
06/16 19:21, 9F
→
06/16 20:03, 2年前 , 10F
基於比較的排序法的話...可以這麼說吧
06/16 20:03, 10F
推
06/17 04:36, 2年前 , 11F
特殊狀況下是有比 quick sort 還快的排序啊，
06/17 04:36, 11F
→
06/17 04:36, 2年前 , 12F
比如 distribution counting 是 O(N)
06/17 04:36, 12F
‣ 更多 MBS550L 的文章
文章代碼(AID): #1WoP7NH4 (C_and_CPP)
C_and_CPP 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 MBS550L 的文章
文章代碼(AID): #1WoP7NH4 (C_and_CPP)