桶排序 Bucket sort

Bucket sort,是一個非比較排序。原理是建立一些桶子,每個桶子對應一資料區間,在將待排序資料分配到不同的桶中,桶子內部各自排序。由於並非比較排序,使用 Bucket sort 需要事先知道資料的範圍與分佈,才能決定桶子對應的區間。

Bucket sort 基本特性如下:

  • 又稱 bin sort
  • 穩定排序:相同鍵值的元素,排序後相對位置不改變。
  • 分配式排序:不透過兩兩比較,而是分析鍵值分佈來排序。特定情況下可達線性執行時間。
  • 預期分佈:資料為均勻分佈

步驟

假設要排序 $n $ 個元素的陣列,這些元素的值平均散落在某個已知的預期範圍內,例如 1 到 100。

  1. Create buckets:建立 $k $ 個桶子(bucket)的陣列。每個桶子對應預期範圍的某區間,如第一個桶子放 1 到 10,第二個放 11 到 20。
  2. Scatter:將每個元素依照該值放入對應的桶子中。
  3. Inner sort:排序所有非空的桶子。
  4. Gather:依序走訪所有桶子,將桶內的元素放回原本的陣列中。

說明

以下用 ASCII diagram 視覺化解釋:

這裡有一些整數,落在 1 至 100 之間。我們有 $n = 10 $ 的陣列要排序。

Original array

+-------------------------------------------------+
|  6 | 28 | 96 | 14 | 74 | 37 |  9 | 71 | 91 | 36 |
+-------------------------------------------------+

1. Create buckets:建立一定數量的桶子,這裡我們建立與原始陣列相同數量的桶子(10)。每個桶子對應 $n - 1 * 10 $ 到 $n * 10 $ 的區間。

Bucket array

+-------------------------------------------------+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+
  ^    ^
  |    |
  |    |
  |    holds values in range 11 to 20
  holds values in range 1 to 10

2. Scatter:將原始陣列中的元素,放入對應的桶中。

Bucket array

  6,9  14   28   37,36               74,71     96,91
  |    |    |    |                   |         |
+-v----v----v----v-------------------v---------v--+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+

3. Inner sort:排序所有非空桶子中的元素,桶內排序可用任意排序法,通常選用「insertion sort」,可確保排序穩定性,並降低額外開銷。

Bucket array

  sort sort sort sort                sort      sort
  ---  --   --   -----               -----     -----
  6,9  14   28   36,37               71,74     91,96
  |    |    |    |                   |         |
+-v----v----v----v-------------------v---------v--+
|    |    |    |    |    |    |    |    |    |    |
+-------------------------------------------------+

4. Gather:排序完後,再將所有桶中元素依序放回原始的陣列。

Original array
+-------------------------------------------------+
|  6 |  9 | 14 | 28 | 36 | 37 | 71 | 74 | 91 | 96 |
+-------------------------------------------------+

效能

Complexity
Worst$O(n^2) $
Best$O(n + k) $
Average$O(n + k) $
Worst space$O(n + k) $ auxiliary

$k $ = 桶子的數量(number of buckets) $n $ = 資料筆數

Worst case

Bucket sort 是一個分配式排序法,對資料分佈有既定的預期:「所有元素平均分佈在每個 bucket 的區間內」。可想而知,最差的狀況是所有元素都聚集(clustering)在同一個 bucket 中,整個 bucket sort 的會退化成單一一個 inner sort 的複雜度。而桶內排序通常選用 insertion sort(最差 $O(n^2) $),所以最差的時間複雜度為「 $O(n^2) $」。

Best case

最佳的狀況則是完全符合預期的平均分佈,一個蘿蔔一個坑,每個桶內排序的最佳時間複雜度為 $O(n / k) $,再乘上桶子總數 $k $,僅需 $O(k \cdot (n / k)) = O(n) $。計算結果看起來非常合理,但實際上最佳時間複雜度為 $O(n + k) $,為什麼呢?

無庸置疑,桶內排序最佳時間複雜度為 $O(n / k) $,但別忘了這是省略常數項過後式子,進行符號運算時,較精確的表達是 $c_0 O(n / k) + c_1 $,對於實作層面的常數 $c_0 $ 和 $c_1 $ 則予以保留。

當我們乘上 $k $,試著算出總運算量時,

$$k \cdot (c_0(n / k) + c_1) $$

會得到:

$$ c_0n + c_1k $$

可以得知,整個計算與 $k $ 有關,所以需要耗時 $O(n + k) $。

撇開數學,我們從 pseudo code 來看。最佳情況下,將所有元素蒐集回陣列的步驟(Gather)如下:

for (each bucket b in all k buckets)
  for (each element x in b)
    append x to the array

最外層的迴圈依桶子數 $k $ 而定,至少需要執行 $k $ 次,複雜度為 $O(k) $。內層的迴圈則是每個桶內的元素都會執行,而我們的資料時均勻分布,因此執行時間與元素總數 $n $ 相關,為 $O(n) $。兩者加起來就是我們所說的 $O(n + k) $ 的最佳複雜度。

那 $k $ 究竟會是多少,影響會比 $n $ 大嗎?

端看桶子總數而定,若桶子總數很大,比元素個數 $n $ 大得多,則桶子總數對執行時間的影響恐較劇烈,就算大多數為空桶子,仍須挨家挨戶查看是否需要執行桶內排序。

Space Complexity

Bucket sort 須額外建立 $k $ 個桶子,每個桶子需要配置長度為 $n $ 的 array,因此空間複雜度為 $O(n \cdot k) $。如果以 dynamic array 實作 bucket,並考慮平攤分析(Amortized analysis),則空間複雜度降至 $O(n + k) $,這也是大多數人接受的分析結果,畢竟不會有人無聊到預先配置 $n \cdot k $ 個 empty bucket。

實作

Bucket

Bucket sort 有許多種各異的實作法,差異最大之處就是桶子 bucket 這部分。


# #![allow(unused_variables)]
#fn main() {
/// Bucket to store elements.
struct Bucket<H, T> {
    hash: H,
    values: Vec<T>,
}

impl<H, T> Bucket<H, T> {
    /// Create a new bucket and insert its first value.
    ///
    /// * `hash` - Hash value generated by hasher param of `bucket_sort`.
    /// * `value` - Value to be put in the bucket.
    pub fn new(hash: H, value: T) -> Bucket<H, T> {
        Bucket {
            hash: hash,
            values: vec![value],
        }
    }
}
#}

這裡的桶子實作兩個 struct fields:

  • values:使用 Vec 儲存對應範圍內的元素
  • hash:Bucket Sort 主函式有一個 hasher 函式,會計算出對應各個桶子的雜湊值,因此要確保桶子的雜湊值有唯一性。

Sorting

接下來就是排序主函式。依照慣例,先看看函式的宣告(function signature)。


# #![allow(unused_variables)]
#fn main() {
pub fn bucket_sort<H, F, T>(arr: &mut [T], hasher: F)
    where H: Ord,
          F: Fn(&T) -> H,
          T: Ord + Clone,
#}

這個 bucket_sort 函式使用了不少泛型:

  • Hhasher 函式的回傳型別,用來辨識不同的桶子。
  • Fhasher 函式自身,只需要一個參數 &T,回傳一個 H
  • T:欲排序資料的型別。

函式自身稍微複雜一點,但仍不脫離四步驟:Create buckets、Scatter、Inner sort,還有 Gather。


# #![allow(unused_variables)]
#fn main() {
pub fn bucket_sort() {
    // ...

    // 1. Create buckets.
    let mut buckets: Vec<Bucket<H, T>> = Vec::new();

    // 2. Scatter
    for value in arr.iter() {
        let hash = hasher(&value); // 2.1.

        let value = value.clone();
        // 2.2.
        match buckets.binary_search_by(|bucket| bucket.hash.cmp(&hash)) {
            // If exists, push the value to the bucket.
            Ok(index) => buckets[index].values.push(value),
            // If none, create and new bucket and insert value in.
            Err(index) => buckets.insert(index, Bucket::new(hash, value)),
        }
    }

    // 3. Inner sort and gather
    let ret = buckets.into_iter().flat_map(|mut bucket| {
        bucket.values.sort(); // 3.1.
        bucket.values
    }).collect::<Vec<T>>();   // 3.2.

    arr.clone_from_slice(&ret); // 4 Copy to original array
}
#}
  1. 一般來說,第一步會配置完所有桶子,但這裡實作僅建立儲存桶子們的容器 buckets,這是由於實作了 hasher 函式,元素對應桶子的邏輯交由外部決定,因此桶子不需事先配置,而是交給第二步驟時 on-the-fly 建立。
  2. 迭代輸入的 arr,將元素散佈到桶子中。
    1. 使用元素值 value 取得雜湊值。
    2. 從一堆桶子內 buckets 尋找對應雜湊值的桶子,如有對應桶子,則將待排序元素插入桶中;若無對應桶子,則馬上建立桶子,並插入待排序元素。
  3. 由於桶子們 buckets 是一個二維陣列集合,我們使用 flat_map 將之壓平。
    1. 使用 Rust 內建 sort(Timsort 的變形)作為我們 inner sort 的實作,將桶內所有元素排好序
    2. 別忘了 Rust 的 Iterator 很 lazy,記得要使用 collect 蒐集 iterator 實作後的結果。
  4. 由於要模擬 in-place 原地排序法的特性,將排序好的資料再次拷貝到 arr 上。這也是為什麼函式元素泛型 T 需要 Clone trait 的原因了。

有關於步驟 2.2.,這部分可以用 HashMap 的變形 IndexMap(一個保存插入順序的有序 HashMap)保存雜湊值對應桶子的資訊,使得外界更容易依雜湊值找到桶子。但為了保持範例程式的簡潔,決定不引入第三方的 crate(Rust 語言第三方模組的代稱),且 binary_search_by 的複雜度為 $O(\log n) $,對 Bucket sort 最差複雜度並無影響。

參考資料