iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列 第 15

Day-15 線性時間演算法 : Bucket sort

bucket sort(桶排序)

假設輸入平均分布,也就是輸入的陣列每一種組合情況都是機率均等的,平均情況下他的時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(n)。和counting sort類似,都是對於輸入做出一些假設,才達到如此快的執行速度,counting sort假設陣列中的每一個元素都是界於1到n之間的整數,而bucket sort也同樣具有這項性質。

假設我們有https://chart.googleapis.com/chart?cht=tx&chl=n個元素的陣列需要排序,每個元素https://chart.googleapis.com/chart?cht=tx&chl=A%5Bi%5D都界於某一個數的區間,如https://chart.googleapis.com/chart?cht=tx&chl=1https://chart.googleapis.com/chart?cht=tx&chl=100

  1. 建立桶子 : 建立https://chart.googleapis.com/chart?cht=tx&chl=k個桶子,每一個桶子對應到某一個預期範圍的數字區間,如第一個桶子放置https://chart.googleapis.com/chart?cht=tx&chl=1https://chart.googleapis.com/chart?cht=tx&chl=10的元素,第二個桶子放置https://chart.googleapis.com/chart?cht=tx&chl=11https://chart.googleapis.com/chart?cht=tx&chl=20的元素,也就是假設元素在https://chart.googleapis.com/chart?cht=tx&chl=1https://chart.googleapis.com/chart?cht=tx&chl=n之間,我們就在等分的劃分成https://chart.googleapis.com/chart?cht=tx&chl=k個區域,將每個區域視為桶子,由於我們假設輸入平均分布,因此不大會出現所有元素都在同一個桶子的情況。
  2. 放置元素 : 將陣列中的元素放到對應的桶子。
  3. 排序 : 使用排序演算法對於每一個桶子中的元素進行排序。
  4. 走訪 : 依序走訪每一個桶子中的元素,並且將元素放回原來的陣列,完成排序。

在bucket sort的程式碼中,我們假設輸入為包含https://chart.googleapis.com/chart?cht=tx&chl=n個元素的陣列https://chart.googleapis.com/chart?cht=tx&chl=A,每一個元素https://chart.googleapis.com/chart?cht=tx&chl=A%5Bi%5D介於某一個數的區間,假設https://chart.googleapis.com/chart?cht=tx&chl=1https://chart.googleapis.com/chart?cht=tx&chl=100,此外,我們還需要額外的空間,https://chart.googleapis.com/chart?cht=tx&chl=B%5B0..n-1%5D當作桶子來存放元素,https://chart.googleapis.com/chart?cht=tx&chl=B陣列中存放的為鏈結串列(linked list),方便我們進行走訪。

BUCKET-SORT(A)
n = A.length
let B[0...n-1] be a new array
for i = 0 to n - 1
    make B[i] an empty list
for i = 1 to n
    insert A[i] into list B[A[i]/10]
for i = 0 to n - 1
    sort list B[i] with insertion sort
concatenate the lists B[0],B[1],...,B[n - 1] together in order


以上面這個例子,就是將陣列中每一個元素依照其數字範圍,如0到10, 11到20依次放入桶子中,接著使用insertion sort對箱子內的元素進行排序,箱子皆為一個鏈結串列,將桶內元素串接再一起,接著從0號箱子開始走訪不是空的桶子,得到排序完成的陣列。

下面是C++實作

#include <iostream>
#include <vector>

using namespace std;
void bucket_sort(int *, int);
void insertion_sort(vector<int> &);
int main(void)
{
    int A[10] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 68};
    bucket_sort(A, 10);
    for (auto i : A)
    {
        cout << i << ' ';
    }
}

void bucket_sort(int *A, int A_length)
{
    vector<int> B[10];
    for (int i = 0; i < A_length; i++)
    {
        int B_index = A[i] / 10;
        B[B_index].push_back(A[i]);
    }
    for (int i = 0; i < 10; i++)
    {
        insertion_sort(B[i]);
    }
    int A_index = 0;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < B[i].size(); j++)
        {
            A[A_index++] = B[i][j];
        }
    }
}

void insertion_sort(vector<int> &B)
{
    for (int i = 1; i < B.size(); i++)
    {
        int key = B[i];
        int j = i - 1;
        while (j >= 0 && B[j] > key)
        {
            B[j + 1] = B[j];
            j--;
        }
        B[j + 1] = key;
    }
}

bucket sort效率

在虛擬碼中總共有3個for迴圈,迴圈主體中除了排序以外,最壞情況下時間複雜度皆為https://chart.googleapis.com/chart?cht=tx&chl=O(n)。假設我們使用的排序為插入排序,需要呼叫n次插入排序。

假設https://chart.googleapis.com/chart?cht=tx&chl=n_i表示桶子https://chart.googleapis.com/chart?cht=tx&chl=B%5Bi%5D中元素個數的隨機變數,插入排序在最差的情況下時間複雜度為https://chart.googleapis.com/chart?cht=tx&chl=O(n%5E2),因此整個bucket sort在最差情況下的時間複雜度可以用下面的式子表示:
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%20%3D%5CTheta(n)%20%2B%5Csum_%7Bi%20%3D%200%7D%5E%7Bn-1%7DO(n%5E2)

下面分析bucket sort在平均情況下的執行時間,也就是對輸入的數據取期望值,我們可以得到執行時間的期望值。
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5BT(n)%5D%20%3DE%5B%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DO(n%5E2)%5D%5C%5C%3D%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DE%5BO(n%5E2)%5D%5C%5C%3D%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DO(E%5B%7Bn_i%7D%5E2%5D)

而這裡要先求出https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5B%7Bn_i%7D%5E2%5D這一項,我們使用指示器隨機變數進行處理,對所有https://chart.googleapis.com/chart?cht=tx&chl=i%20%3D%200..n-1https://chart.googleapis.com/chart?cht=tx&chl=j%3D1...nhttps://chart.googleapis.com/chart?cht=tx&chl=i表示桶子的index, https://chart.googleapis.com/chart?cht=tx&chl=j表示陣列中元素的index,https://chart.googleapis.com/chart?cht=tx&chl=I表示由桶子所組成的陣列,https://chart.googleapis.com/chart?cht=tx&chl=A表示待排序的元素所在的陣列
https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D%3DI%5Cbegin%7BBmatrix%7DA%5Bj%5D%5C%20falls%5C%20in%5C%20bucket%5C%20i%5Cend%7BBmatrix%7D
這裡https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D表示https://chart.googleapis.com/chart?cht=tx&chl=A%5Bj%5D放入桶子的事件,發生表示1,反之為0。https://chart.googleapis.com/chart?cht=tx&chl=n_i表示桶子https://chart.googleapis.com/chart?cht=tx&chl=B%5Bi%5D中元素個數的隨機變數,因此這裡可以使用指示器隨機變數的和去表示元樹的隨機個數
https://chart.googleapis.com/chart?cht=tx&chl=n_i%3D%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D

接著為了計算https://chart.googleapis.com/chart?cht=tx&chl=E%5B%7Bn_i%7D%5E2%5D,將平方項展開
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5B%7Bn_1%7D%5E2%5D%3DE%5B(%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D)%5E2%5D%3DE%5B%5Csum_%7Bj%3D1%7D%5En%5Csum_%7Bk%3D1%7D%5EnX_%7Bij%7DX%7Bik%7D%5D%3DE%5B%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D%5E2%2B%5Csum_%7B1%3C%3Dj%3C%3Dn%7D%5Csum_%7B1%3C%3Dk%3C%3Dn%2C%5C%5Ck!%3D%20j%7DX_%7Bij%7DX_%7Bik%7D%5Dhttps://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5C%5C%3D%5Csum_%7Bj%3D1%7D%5EnE%5BX_%7Bij%7D%5E2%5D%2BE%5B%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D%5E2%2B%5Csum_%7B1%3C%3Dj%3C%3Dn%7D%5Csum_%7B1%3C%3Dk%3C%3Dn%2C%5C%5Ck!%3D%20j%7DE%5BX_%7Bij%7DX_%7Bik%7D%5D

指示器隨機變數https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D,表示https://chart.googleapis.com/chart?cht=tx&chl=A%5Bj%5D放入桶子https://chart.googleapis.com/chart?cht=tx&chl=I%5Bi%5D的事件,發生的機率為https://chart.googleapis.com/chart?cht=tx&chl=1%2Fn,當此事件發生時,https://chart.googleapis.com/chart?cht=tx&chl=X_%7Bij%7D為1,因此
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5BX_%7Bij%7D%5E2%5D%3D1%5E2*%5Cfrac%201%20n%2B0%5E2*(1-%5Cfrac%201%20n)%3D%5Cfrac%201%20n
而在https://chart.googleapis.com/chart?cht=tx&chl=k!%3Dj時,
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5BX_%7Bij%7DX_%7Bik%7D%5D%3DE%5BX_%7Bij%7D%5DE%5BX_%7Bik%7D%5D%3D%5Cfrac%201%20n%20*%20%5Cfrac%201%20n%20%3D%20%5Cfrac%201%20%7Bn%5E2%7D

將以上兩個式子代回https://chart.googleapis.com/chart?cht=tx&chl=E%5B%7Bn_i%7D%5E2%5D

https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5B%7Bn_i%7D%5E2%5D%3D%5Csum_%7Bj%3D1%7D%5EnE%5BX_%7Bij%7D%5E2%5D%2BE%5B%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D%5E2%2B%5Csum_%7B1%3C%3Dj%3C%3Dn%7D%5Csum_%7B1%3C%3Dk%3C%3Dn%2C%5C%5Ck!%3D%20j%7DE%5BX_%7Bij%7DX_%7Bik%7D%5D%20https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5C%5C%3D%5Csum_%7Bj%3D1%7D%5En%5Cfrac%201%20n%2BE%5B%5Csum_%7Bj%3D1%7D%5EnX_%7Bij%7D%5E2%2B%5Csum_%7B1%3C%3Dj%3C%3Dn%7D%5Csum_%7B1%3C%3Dk%3C%3Dn%2C%5C%5Ck!%3D%20j%7D%5Cfrac%201%20%7Bn%5E2%7D%5C%5C%3Dn*%5Cfrac%201%20n%2Bn(n-1)*%5Cfrac%201%20%7Bn%5E2%7D%5C%5C%3D1%2B%5Cfrac%20%7Bn-1%7D%20n%5C%5C%3D2%20-%20%5Cfrac%201%20n

而我們上面得到的執行時間期望值為
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20T(n)%20%3D%5CTheta(n)%20%2B%5Csum_%7Bi%20%3D%200%7D%5E%7Bn-1%7DO(n%5E2)
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20E%5BT(n)%5D%20%3DE%5B%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DO(n%5E2)%5D%5C%5C%3D%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DE%5BO(n%5E2)%5D%5C%5C%3D%5CTheta(n)%2B%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7DO(E%5B%7Bn_i%7D%5E2%5D)

https://chart.googleapis.com/chart?cht=tx&chl=E%5B%7Bn_i%7D%5E2%5D代換,得到
https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20%5CTheta(n)%2Bn*O(2-1%2Fn)%3D%5CTheta(n)

所以即使輸入的輸入不是均勻分布的,也就是數據不一定式平均分在散某一個區間,bucket sort還是能夠在線性時間內完成,只要符合以下性質

  • 所有桶大小的平方和與陣列中元素的總數呈現線性關係

那麼bucket sort還是可以在線性時間內完成。

p.s: 感謝MuMu大大介紹displaystyle這個排版方式~~

參考資料:Introduciton to algorithms 3rd


上一篇
Day-14 線性時間演算法 : Radix sort
下一篇
Day-16 雇用問題, 指示器隨機變數(indicator random variable), 隨機化演算法
系列文
從0開始啃Introduction of algorithms心得與記錄30

尚未有邦友留言

立即登入留言