[問題] 用最少比較次數找最大、最小等值

[lionhome20 (林北大GG)]

各位神人好

想請問在int array[5000]裡

如何用最少的compare次數

找出最大 最小 次大 次小的值

有沒有小於下列5000*4次 compare的找法

(找每一個數都用暴力法)
for(i=0;i<5000;i++)
    if(array[i] > Max)
    Max = array[i]

感謝




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.122.2
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1459419175.A.56B.html
推 LPH66: 概念: 一個數沒比過不會知道他是不是最大
感謝提醒 已修正題目 目前有想到用Heap sort
※ 編輯: lionhome20 (111.248.31.18), 03/31/2016 22:20:19
推 springman: 同時找最大與最小，有 5000*3/2 次比較的方法。
→ springman: 找最大與次大，有 n + log_2 n 次比較的方法。
→ springman: 所以看來應該有 5000*3/2 + 2*log_2 5000 次比較的方法
→ springman: 找到這四個資料，只是程式寫起來或許比較麻煩。
推 DJWS: sorting network  這是超級困難的問題
推 FRAXIS: sorting network 的限制應該太強了吧
推 FRAXIS: 因為 sorting network 不能依照之前比較的結果來選擇下
→ FRAXIS: 一次要比較的元素
推 DJWS: 對耶  那麼  樓上說的這種情況  有沒有專有名詞？
推 FRAXIS: decision tree?
推 janice001: 都n log n 了 幹嘛不直接quick sort?
推 j2jx008447: 樓上的方法排序後，索引值頭尾不就是答案了嗎