mRC.-
Lv 7
mRC.- 發問時間: 電腦與網際網路程式設計 · 1 0 年前

關於 ordination methods 的疑問

...小弟在家自學 C 語言遇到困難,有請各位先進伸手...扶持一二...不勝感激...

...正因為是自學的關係,希望答題的大大能盡量詳細的將每個步驟列出...以便對照書本...

請問:「想要將某一組整數按順序排列,在 MergeSort, BucketSort, BubleSort 及 ShellSort 之中,何者最費力以及最不費力,」?

4 個解答

評分
  • 1 0 年前
    最佳解答

    1. 費力的定義不明

    2. 整數有沒有上下限定義

    因此,難有〝標準〞答案

    2009-03-19 06:22:16 補充:

    首先,請觀查各類物品價位表:

     品名  原價  漲價   體積

    Bucket: O(n*k)  O(n2*k)  O(n*k) // k: 輸入範圍

    Merge: O(n log n) O(n log n) O(n)

    Shell:    O(_)  O(n log2 n) O(1)

    Bubble:   O(n2)  O(n2)   O(1)

    尤於題意不清,很難有〝標準〞答案。

    1. bucket 要有範圍。在 k 接近 n 時,它很差!

     如:200位員工薪水,從 16789 到 98765!

     時空都是:O(200 * 98765) 遠大於 O(n3) = O(200*200*200) @.@

     這是什麼爛方法?

     但全校學生:2萬,學生單科成績 0 ~ 100,這就不差!

     雖然 O(2萬 *101) 比 O(2萬 * 14.288) = O(n log n) 差,

     但因沒有比較、沒有交換!bucket會比較快!

    2. Merge 一般而言是最好的(In general, Quick 更好,但不在這清單內)

     而且它有 in-place 變化版,空間會是 O(1)!

     (這變化版,同大小的值,排出來後,順序不會照原序。)

    3. Shell 在小資料 及 原資料接近排好序上,接近稱王!

     據說,連 最佳化過的 Quick Sort 都贏不了它。

     但資料量一大(也沒多大,才大於一千),就不行了!

     註:Shell 的原原原價是 O(n2)。

       各類的 variation出現後,目前原價不詳。

    4. Bubble 只適用於教學,真實世界,一個學過的程式師,不可能用它!

    另外,Big-O 只適用於大資料量!用它來看小資料量,是個笑話!

    至於約多大?不一定。

    也就是說:資料量太小的情況下,上述全是錯的!

    如:最最最最佳化過的〝純〞QuickSort,在 n < 20時,是輸給 O(n2) 的 insertion sort 的!

    所以,〝純〞QuickSort也只會出現在學生作業裡!

    一但分割後資料量小於某個門檻,一定要換別的 Algorithm 去做!

    這是個不變的原則!任何 D&C 的 Alg,都必須如此!

    (含目前很熱的 平行運算!

     它要做雙重這方面的考慮!!

    另註:D&C 在有 Cache 的環境下,會自動被 Cache 加速!

    所以,寫得好的 D&C,測起來會比非 D&C 的理論快得多。

    (註:要知道這個,要看 Hidden constant!)

  • mRC.-
    Lv 7
    1 0 年前

    Jacob Lee 您好,如果「費力」以程式運作時間及採用最極端的 case 來解釋,是否比較清楚?

    另外,整數無上下限定義。

  • 鴨子
    Lv 6
    1 0 年前

    http://zh.wikipedia.org/w/index.php?title=%E6%8E%9...

    各別 sort 的作法, 進入連結的 page

  • 鳳綾
    Lv 4
    1 0 年前

    既然是自學,怎會問這種學校作業問題?

    你先解釋一下MergeSort, BucketSort, BubleSort 及 ShellSort的作法~

還有問題?馬上發問,尋求解答。