bucket_sort

桶排序 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 這部分。

/// 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）。

pub fn bucket_sort<H, F, T>(arr: &mut [T], hasher: F)
    where H: Ord,
          F: Fn(&T) -> H,
          T: Ord + Clone,

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

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

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

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 最差複雜度並無影響。

參考資料

• Wiki: Bucket sort
• Wiki: Amortized analysis
• How is the complexity of bucket sort is O(n+k) if we implement buckets using linked lists?
• Bucket sort in Rust