# Lecture 08 - Counting sort
> 課程內容 : 中興大學資工系 范耀中教授 (112 學年度第 2 學期)
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## 1. Introduction
Counting sort 能做到對時間複雜度為 $O(n)$ 的排序，以下簡述之。

假設有一個陣列為 [e, a, c, d, e, a, e]，統計字母的出現順序如下


Counting sort 的核心概念其實就是依照字統計後出現的次數加字母(或數字)依序填入陣列之中，最後可得 [a, a, c, d, e, e, e]

依照上述 counting sort 的概念，由累加值所計算出位移量所代表的意思是該第一個該字母要擺放的位置，例如 :
* a 的位移數 = 0，表示第一次出現的 a 要放在 index 0 的位置
* b 的位移數 = 2，表示第一次出現的 b 要放在 index 2 的位置
* c 的位移數 = 2，表是第一次出現的 c 要放在 index 2 的位置
* 但因為第一個 b 也是放在 index 2，由此可知這個序列沒有 b 這項元素

後續依此推類

## 2. 操作原理

##### 該如何做排序 ?
在 scan 陣列的過程中，掃描到哪個字母，則

* 找到該字母的位移數並填入 array 的對應位置
* 此概念即是上述所說，第一個該字母要擺放的位置
* 位移數 + 1
* 此概念表示，因為該字母已經放入一個了，所以位移量要 +1 來計算擺放第二個該字母的位置


## 3. 效能
以長度為 N 的陣列為例

* Counting : N
* Accumulate : N
* Shift : N
* Placing : N

時間複雜度為 4N，是一個 $O(N)$ 等級的 sorting algorithm

## 4. 缺點
以字母排序 [a, b, c, a, d, d, z] 為例，使用 counting sort 的話需要建立一個 26×26 的表格，且表格中有很多的 0 在相加，需要付出多餘的空間成本