Counting sort

Input :
Output :
Aux(auxiliary) array :

Counting sort假設一個陣列中有個整數，每一個整數都是在0到k範圍內。

對於每一個輸入的元素x，確認小於x的元素個數，就可以把x放在陣列中正確的位置上了

COUNTING-SORT(A, B, k)
    let C[0...k] be a new array
    for i = 0 to k
        C[i] = 0
    for j = 1 to A.length
        C[A[j]] = C[A[j]] + 1
    //C[i] now contains the number of elements equal to i.
    for i = 1 to k
        C[i] = C[i] + C[i - 1]
    //C[i] now contains the number of elements less than or equal to i.
    for j = A.length downto 1
        B[C[A[j]]] = A[j]
        C[A[j]] = C[A[j]] - 1

Example:

A = 4,1,3,4,3    C = 0,0,0,0
i = 1,2,3,4,5    i = 1,2,3,4(A陣列中最大值為4，因此k = 4)
___________________________________________________
A = 4,1,3,4,3    C = 0,0,0,1
    ^
    j            從A[0]開始走訪，發現出現4，因此在C[4]的地方加1，表示4出現過一次
___________________________________________________
A = 4,1,3,4,3    C = 1,0,0,1
      ^
      j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,1,1
        ^
        j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,1,2
          ^
          j
___________________________________________________
A = 4,1,3,4,3    C = 1,0,2,2
            ^
            j
___________________________________________________
接著，為了方便演示，我們產生出一個新的陣列C'
C = 1,0,2,2
C' = 1,0+1,2+0+1,2+2+0+1

陣列C'表示和前一個數字的加總
C' = 1,1,3,5
C'[1]意義為有1個數字小於等於1
C'[2]意義為有1個數字小於等於2
C'[3]意義為有3個數字小於等於3
C'[4]意義為有5個數字小於等於4

C會被C'所取代
___________________________________________________
接著將元素依序放入B，產生出完成排序的陣列
先取出A的最後一個元素A[j]，並看到C[A[j]]，也就是在計數器中對應的數值，
這個數值表示A[j]在B陣列中的位置，將該數值放到B陣列中
    A = 4,1,3,4,3    C = 1,1,3,5     B = 0,0,3,0,0
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
                ^            ^               ^
                j           A[j]          C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,2,5     B = 0,0,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
              ^                ^                 ^
              j               A[j]            C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,2,4     B = 0,3,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
            ^                ^             ^  
            j               A[j]         C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 1,1,1,4     B = 1,3,3,0,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
          ^              ^               ^
          j             A[j]          C[A[j]]
___________________________________________________
    A = 4,1,3,4,3    C = 0,1,1,4     B = 1,3,3,4,4
index = 1 2 3 4 5        1 2 3 4         1 2 3 4 5
        ^                      ^               ^    
        j                     A[j]          C[A[j]]

得到B，即完成排序。

陣列的作用基本上是一個計數器，這個計數器告訴我們應該擺放在B的位置，也就是B的index。

以來說，表示任何為數值為4的元素他擺放的位置應該要在B的index 5或是更前面的位置。

，這個計數器的意義
如果出現元素數值為1，他所在的位置為B陣列中 index 1或以前的位置
如果出現元素數值為2，他所在的位置為B陣列中 index 1或以前的位置
如果出現元素數值為3，他所在的位置為B陣列中 index 3或以前的位置
如果出現元素數值為4，他所在的位置為B陣列中 index 5或以前的位置

使用C++進行實作

#include <iostream>

using namespace std;
void counting_sort(int *, int *, int, int);
int main(void)
{
    int array_1[5] = {4, 1, 3, 4, 3};
    int *array_2 = (int *)malloc(sizeof(int) * 6);
    counting_sort(array_1, array_2, 4, 5);
    for (int i = 1; i < 6; i++)
    {
        printf("%d ", array_2[i]);
    }
}

void counting_sort(int *A, int *B, int k, int a_lenght)
{
    int *C = (int *)malloc(sizeof(int) * (k + 1)); //index 0 ~ k
    for (int i = 0; i < (k + 1); i++)
    {
        C[i] = 0;
    }
    for (int j = 0; j < a_lenght; j++)
    {
        C[A[j]] = C[A[j]] + 1;
    }
    for (int i = 1; i <= k; i++)
    {
        C[i] = C[i] + C[i - 1];
    }
    for (int j = a_lenght - 1; j >= 0; j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] = C[A[j]] - 1;
    }
}

效率分析

在counting_sort主體中，第一個for需要的時間，第二個for需要的時間(n表示陣列長度)，第三個for需要的時間，第四個for需要的時間，整個counting_sort所需要的時間為，當時，整個counting_sort為，即為線性時間。

我們得知如果要使counting_sort十分的高效，需要確保陣列中的元素在某一個不會太大的整數範圍內，如果陣列中的數字最多只會到陣列長度，也就是的概念，那麼陣列的長度也會為，即可實現出線性時間的演算法。

由於我們跳脫出了比較排序的演算法模型，即為元素和元素之間需要比較大小，我們使用計數器去確認元素所需要擺放的位置，因此，counting_sort的時間下界要比比較排序模型的時間下界來得好。

演算法穩定性

演算法穩定性指的是如果在一個待排序的陣列中，有兩個相同的元素，如果在排序後這兩個元素相對位置保持不變，那麼該演算法就是穩定的，像是上面的例子出現了兩個4和兩個3，他們在排序後相對次序皆沒有改變，因此我們可以說counting_sort是穩定的演算法。

參考資料:Introduction to algorithms