---
# System prepended metadata

title: Chap. 07- Sort
tags: [資料結構]

---

# Chap. 07 - Sort

> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
> 
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Content
* [簡單排序](#簡單排序)
    * [1. Bubble sort](#1-Bubble-sort)
    * [2. Selection sort](#2-Selection-sort)
    * [3. Insertion sort](#3-Insertion-sort)
    * [4. Shell sort](#4-Shell-sort)
* [高效排序](#高效排序)
    * [1. Merge sort](#1-Merge-sort)
        * [1.1 Top-down merge sort](#11-Top-down-merge-sort)
        * [1.2 Bottom-up merge sort](#12-Bottom-up-merge-sort)
    * [2. Quick sort](#2-Quick-sort)
    * [3. Heap sort](#3-Heap-sort)
* [排序演算法的極限](#排序演算法的極限)
* [混合排序](#混合排序)
    * [1. Tim sort](#1-Tim-sort)
* [特殊排序](#特殊排序)
    * [1. Bucket sort](#1-Bucket-sort)
    * [2. Counting sort](#2-Counting-sort)
    * [3. Key-based sort](#3-Key-based-sort)
    * [4. Radix sort](#4-Radix-sort)

## 簡單排序
### 1. Bubble sort

> The following code is saved in `sorted.c`.

```c=
// bubble sort
void bubbleSort(int arr[], int n){
    int temp;

    for (int i = 0; i < n-1; i++){
        for (int j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                temp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}
```

### 2. Selection sort

最簡單的排序法之一，**每次挑選==最小==(最大)元素放到正確的位置**，過程如下：

* 從陣列左側(index=0)開始，搜尋整個 unsorted array 並挑選最小值
* 將最小值與 unsorted array 的左側元素(index=0)交換
* 此時左邊(index=0)會是 sorted array，右邊會是 unsorted array
* 從下一個 index 開始繼續上述步驟，直到排序完成

> The following code is saved in `sorted.c`.

```c=
// selection sort
void selectionSort(int arr[], int n){
    int temp;

    for (int i = 0; i < n - 1; i++){
        int minIndex = i;
        
        // compare and search the minimum element
        for (int j = i + 1; j < n; j++){
            if (arr[j] < arr[minIndex]){
                minIndex = j;
            }
        }
        // swap the minimum and current element
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
```

#### Analysis

* Time complexity: $O(n^2)$
因為排序過程中每個位置都需要尋找最小值才能決定
* Space complexity: $O(1)$
* Advantage
    * Unstable
    * In-place
### 3. Insertion sort

<img src="https://media.geeksforgeeks.org/wp-content/uploads/20240802210251/Insertion-sorting.png" width="600">

(圖片來源：[GeeksforGeeks](https://www.geeksforgeeks.org/insertion-sort-algorithm/))


Insertion sort 的基本概念是將元素**插入到一個已經排序好的 array 之中**並放在**正確的位置**，插入後的陣列依然是**已經排序**好的。

假設有兩個陣列，一個已經排序好(sorted)，另一個尚未排序(unsorted)。Insertion sort 的過程就是每次從 unsorted array 中挑選一個數字插入到 sorted array 中的正確位置。

:::info
可以想像成類似卡牌的插入，手上有兩疊卡牌，一疊有排序一疊沒有，從沒有排序的卡牌中每次挑選一張放在已排序卡牌中的正確位置。
:::

Insertion 的**關鍵第一步**是如何在一個**尚未排序的 array 中==選出已經排序好的 sub-array==**

* 將 array 的**首項元素 `arr[0]` 視為 sorted array**
* 將第 2 個元素 `arr[1]` 與第 1 個元素 `arr[0]` 做**比較(comparison)**
    * 若 `arr[1] < arr[0]` 則交換(swap)兩者位置
    * 若 `arr[1] >= arr[0]` 則不變
* 繼續拿第 3 個元素往前與前 2 個元素**依序做比較插入**

:::info
交換(swap)的過程中需要第三方元素來暫存舊的值，最後再換回。以 $A \leftrightarrow B$ 互換為例：

* $A \rightarrow X$
* $B \rightarrow A$
* $X \rightarrow B$

在進行 insertion sort 時因為需要做連續的比較交換，所以可以等**最後確定後再將元素放入正確位置**
:::

> The following code is saved in `sorted.c`.

```c=
// insertion sort
void insertionSort(int arr[], int n){
    int i;   // i point the bound of sorted array.
    int j;   // j used to compare with key and swap them.
    int key; // an element which is going to be compared and inserted correct position.
    
    for (i = 1; i < n; i++){
        key = arr[i];
        j = i - 1;

        while ((j >= 0) && (arr[j] > key)){
            arr[j+1] = arr[j];
            /** if you want to track the change of input array in each iteration
             * try these two lines.
             * arr[j] = key;
             * printArray(arr, n);
            */
            j = j - 1;
        }
        arr[j+1] = key;
    }
}
```

每一次迭代過程中都要將 `key` 放入正確的位置，所以將 `key` 不斷往前比較

* 比 `key` 大，交換：`arr[j+1] = arr[j];`
* 比 `key` 小，正確位置，將 `key` 插入：`arr[j+1] = key;`

#### Analysis

* Time complexity
    * Best case
    最好的的情況是 array 本身已經排序好，時間複雜度為 $O(n)$
    * Worse case
    如果 array 是反向的遞減排序(reverse sorted)，則每次插入的元素都需要不斷比較交換直到放在第一個，時間複雜度為 $O(n^2)$
    * Average case
    如果 array 是隨機排序，時間複雜度為 $O(n^2)$
* Space complexity
排序過程不需要額外的空間，空間複雜度為 $O(1)$，是一種 in-place 的排序法。
* Advantage
    * 對長度較小且快排好的 array 有比較好的效率，適用於長度較小的 array
    * Stable
    * In-place

:::info
排序演算法的穩定性(stability)指的兩個元素值相同的情況下，排序後的順序與排序前的順序相同。例如考慮以下陣列

$$
[6,\ 2,\ 3^*,\ 4,\ 1,\ 3, 9]
$$

若某個排序演算法執行後的結果是

$$
[1,\ 2,\ 3^*,\ 3,\ 4,\ 6,\ 9]
$$

則該排序演算法具有 stable 的性質，因為 $3^*$ 與 $3$ 的順序相同。反之若結果為

$$
[1,\ 2,\ 3,\ 3^*,\ 4,\ 6,\ 9]
$$

則為 unstable 的排序法
:::

### 4. Shell sort

Shell sort 是基於 insertino sort 的以下性質進行改良的排序演算法：

* 對幾乎排好的資料來說 insertion sort 的執行效率高
* 但大部分情況效率很差，因為排序過程中每次只能移動一個元素

為了解決 insertion sort 的第二個缺點，shell sort 採用的是將原始資料切割成小資料，因為小資料可以視為幾乎排序好的陣列，對每個陣列都進行 insertion sort 後可將原始資料排序完成

Step-by-step：

* 依照間隔長度 h，每 h 個元素取出來形成 subarray
* 以 insertion sort 將每個 subarray 排序(排序後的 subarray 稱為 h-sorted array)
* 縮小間隔長度 h 重複第一步

以 [23, 1, 10, 5, 2] 為例，若 h = 2，則 subarray 為 [23, 10, 2] 與 [1, 5]

> The following code is saved in `sorted.c`.


```c=
//shell sort
void shellSort(int arr[], int n){
    int h;    // control subarray size
    int i, j; // used to perform insertion sort

    for (h = n / 2; h > 0; h /= 2){
        for (i = h; i < n; i++){
            int temp = arr[i];

            for (j = i; j >= h && arr[j-h] > temp; j -= h){
                arr[j] = arr[j-h];
            }
            arr[j] = temp;
        }
    }
}
```

## 高效排序
### 1. Merge sort

合併排序法(merge sort)是一種利用 **divide and conquer** 的概念所衍生的排序演算法。依照合併方向的不同可以分為兩種作法：

* Top-down(recursion ver.)
* Bottom-up(iteration ver.)

#### 1.1 Top-down merge sort

<img src="https://media.geeksforgeeks.org/wp-content/uploads/20230706153706/Merge-Sort-Algorithm-(1).png" width=600>

(圖片來源：[GreekforGreek](https://www.geeksforgeeks.org/merge-sort/))

第一種 merge sort 是**由上而下(top-down)的方向**，是遞迴版本的 merge sort。將長度為 n 的陣列不斷分割成大小相同的兩個子陣列，每個子陣列，將子陣列排序完後再依序合併。

**Step-by-step：**

* 使用遞迴的方式不斷**分割輸入陣列**，直到不能分割為止(長度=1)
* 從最**小的子陣列開始獨自排序**
* 排序完後使用 **merge algorithm 兩兩合併**，直到所有子陣列合併成輸入陣列長度

> The following code is saved in `sorted.c`.

```c=
// merge sort
void merge(int arr[], int left, int middle, int right, int *mergedArray){
    /** merge left and right sub-array and assign to mergedArray
     * Parameter:
     *     left: index of left point which is beginning of left sub-array
     *     middle: index of middle point which is the partition point also
     *     right: index of right point which is the end of right sub-array
    */
    
    int i = left;       // control left sub-array
    int j = middle + 1; // control right sub-array
    int k = left;       // control merged list

    while ((i <= middle) && (j <= right)){
        if (arr[i] <= arr [j]){
            mergedArray[k++] = arr[i++]; // assign i/k then plus 1
        }
        else{
            mergedArray[k++] = arr[j++];
        }
    }

    // assign remaining sub-array if another done
    while (i <= middle){
        mergedArray[k++] = arr[i++];
    }
    while (j <= right){
        mergedArray[k++] = arr[j++];
    }

    // copy to original array
    for (i=left; i<=right; i++){
        arr[i] = mergedArray[i];
    }
}

void topDownMergeSort(int arr[], int left, int right, int *mergedArray){
    int middle = left + (right - left) / 2;

    if (left < right){
        topDownMergeSort(arr, left, middle, mergedArray);    // divide left sub-array
        topDownMergeSort(arr, middle+1, right, mergedArray); // divide right sub-array
        merge(arr, left, middle, right, mergedArray);
        /**
         * if you want to show the sorting procedure
         * add a parameter 'n' which is the lenght of input array 'arr'
         * then uncomment the following code
         * printArray(arr, n); // show sorting pdocedure 
         */
    }
}
```

#### 1.2 Bottom-up merge sort

Top-down 的 merge sort 是以遞迴的方式呈現，比較**適合用在小資料**上，若是在大資料上做遞迴函式則會需要較大的 stack space，空間不夠可能會導致**溢位(overflow)**

Bottom-up 是 top-down 的反向做法，排序過程**不會涉及陣列的分割(partition)**，因為預設每次的分割長度都是以 $2^n$ 為單位。

**Step-by-step：** 給定一個 size = n 的輸入陣列，

* 對於 size = 1 的子陣列可以視為已經排序好的子陣列
* 將所有 size = 1 的子陣列**兩兩合併**，形成 size = 2 的已排序子陣列
* 對於所有 size = 2 的子陣列兩兩合併，形成 size = 4 的已排序子陣列
* 依此類推，直到合併兩個 size = n / 2 的已排序子陣列

> The following code is saved in `sorted.c`.

```c=
// merge sort
#define MIN(x, y) ((x) < (y) ? (x) : (y))

void bottomUpMergeSort(int arr[], int n, int *mergedArray){
    int currSize;// current size of each sub-array
    int left; // leftmost index of left sub-array

    // merge sub-arry of size n to create sorted array of size 2*n
    for (currSize = 1; currSize <= n-1; currSize *= 2){

        // pick beginning point of each sub-array of size currSize
        for (left = 0; left < n-1 ; left += 2 * currSize){
            int middle = MIN(left + currSize - 1, n - 1);    // end index of left sub-array
            int right = MIN(left + 2 * currSize - 1, n - 1); // end index of right sub-array
            merge(arr, left, middle, right, mergedArray);
            //printArray(arr, n); // if you want to show the sorting process, uncomment this line
        }
    }
}
```

* **外層**迴圈控制的是 **array size**
    * 合併的陣列長度不能超過輸入陣列(`currSize = n - 1`)
    * 每次合併的陣列長度是以**指數形式遞增**(`currSize *= 2`)
* **內層**迴圈是計算兩兩**合併過程中陣列的==頭尾==位置**
    * 左子陣列的起點必須小於倒數第 2 個位置(`left < n - 1`)
    * 合併後的子陣列長度為 2 * currSize，所以左子陣列的計算必須每次遞增 2 倍長度(`left += 2 * currSize`)
    * 左子陣列的起點位置必須在 `left + currSuze - 1` 與最後一個元素 `n-1` 做選擇，避免超出輸入陣列的邊界
    * 右子陣列的結束位置必須在 `left + 2 * currSize - 1` 與最後一個元素 `n - 1` 做選擇，避免超出輸入陣列的邊界

#### Analysis

* Time complexity
兩個方式的時間複雜度都是 $O(n\cdot \log n)$，因為分割過程中樹的高度是 $\log n$ 且每層都有 n 個元素需要做排序。
* Space complexity
不論是 top-down 或 bottom-up 的做法，在排序過程中都需要一個額外的陣列來儲存合併後的已排序陣列(not in-place)，所以空間複雜度都是 $O(n)$。但因為遞迴版本會不斷呼叫函式並儲存在 stack 中，因此從記憶體的角度上看，遞迴版本的空間複雜度是 $O(n+\log n)$
* Advantage
    * Stable
    在合併過程中，會優先選擇較小的元素，但當元素大小相同時，會優先選擇放在左子陣列，所以元素會保持輸入時的相對順序，是一種 stable 的排序方法。
    * Not inplace

### 2. Quick sort

![image](https://media.geeksforgeeks.org/wp-content/uploads/20240926172924/Heap-Sort-Recursive-Illustration.webp)
(圖片來源：[GreekforGreek](https://www.geeksforgeeks.org/quick-sort-algorithm/))

快速排序法(quick sort)同樣是依據 **divide and conquer** 的精神來進行排序，將要排序的**大陣列依序拆解成許多小陣列**，當小陣列排序好之後，則大陣列也會排序完成。

* 選定一個 **樞紐(pivot)** 並將 array 中的元素依照下列規則**重新排列並分解**成兩個 sub-array
    * $\le$ pivot 的數放在 pivot 左邊
    * $\ge$ pivot 的數放在 pivot 右邊
* 對左右兩個 sub-array 繼續依照上述步驟遞迴分割(partition)
* 直到最後的 array 只剩一個元素時就排序完成

(類似 binary search tree 的規則)

:::info
做 array partition 的目的是將每次**選定的 pivot 放在正確的位置上**
:::

快速排序法的實作關鍵在於以下兩點：(1) 如何挑選 pivot 與 (2) 如何對 array 做 partition

(1) How to choose pivot
一般來說 pivot 會直接挑選每次迭代過程中 array 的首項或末項元素。但如果剛好選到最大或最小值，則樹的高度會 = n。而如果挑到的 pivot 剛好是中位數，則可以形成一個高度為 $\log n$ 的 balance binary tree。

因次為了避免選到最大或最小值，可以每次選擇 3 個數並取三數的中位數做為 pivot

(2) How to partition an array
迭代過程中分割 array 的過程有很多種，常見的有

1. Naive partition
Naive partition 在分割過程中，會複製整個 array。將較小的元素放在 left sub-array，較大的元素放在 right sub-array。空間複雜度為 $O(n)$

2. Lomuto partition
Lomuto partition 在分割過程中會追蹤較小的元素。從陣列首項開始迭代，當遇到較小(smaller than pivot)的元素就跟當前的元素交換位置

3. **Hoave's partition**
Hoave's partition 使用 two pointer 的方式來分割陣列，選定 pivot 之後(通常是陣列第一個元素)
    * 當左指標元素 > pivot 且右指標元素 < pivot 時交換位置
    * 直到左指標 index >=  右指標 index 則完成分割

> The following code is saved in `sorted.c`.

```c=
// quick sort
void swap(int *a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int left, int right){
    /** Hoare's Partition Algorithm
     * use two pointers to divide the input array
     * this method also called Hoare's Partition Algorithm
     * Parameter:
     *    left: index of the beginning element of arr
     *    right: index of the last element of arr
    */

    int leftPointer = left - 1;
    int rightPointer = right + 1;
    int pivot = arr[left];

    while (1){
        do { // left pointer
            leftPointer++;
        } while (arr[leftPointer] < pivot);

        do { // right pointer
            rightPointer--;
        } while (arr[rightPointer] > pivot);

    if (leftPointer >= rightPointer) return rightPointer;
    swap(&arr[leftPointer], &arr[rightPointer]);
   }
}

void quickSort(int arr[], int left, int right){
    /** use Hoare's partition to implement quick sort
     * Parameter:
     *     left: index of beginning element.
     *     right: index of last element.
     */
    
    if (left < right){
        int partiionIndex = partition(arr, left, right);
        quickSort(arr, left, partiionIndex);    // sort left array
        quickSort(arr, partiionIndex+1, right); // sort right array
    }
}
```

#### Analysis

* Time complexity
    * Worse case
    如上所述，每次在挑選 pivot 時，如果剛好都選到最大或最小，則會形成一個高度 = n 的 skewed tree，時間複雜度為 $O(n^2)$
    * Best case
    同樣的，如果每此都剛好選到中位數，則會形成一顆高度 = $\log n$ 的 balanced tree，時間複雜度為 $O(n \log n)$
    * Average case：$O(n \log n)$
* Space complexity
依照迭代不同，空間複雜度也不同，通常是 $O(\log n)$ 或 $O(n)$
* Advantage
    * Unstable
    * Not in-place


### 3. Heap sort

堆積排序(heap sort)是使用 max heap 的結構來實現排序的過程。因此在實際排序之前，必須先將輸入陣列的順序改成 max heap 的結構。

* 將輸入陣列調整成 max heap
* 將 root 與 max heap 中的最後元素 last 交換位置，此時 last 的值最大，已經排序完成
* 移除 last
* 最後將剩下元素再次調整成 max heap，重回第二步驟

:::info
Heap 的陣列表示法中，習慣上會用 1-index 表示根節點的位置來簡化計算。此處因為要進行排序所以使用 0-index 來表示根節點的位置。
:::

在 heapSort 前半段的目的是要讓輸入陣列形成最大堆積，所以從底層的葉子節點開始往上處理，但因為葉子節點可以視為已經排序好的 heap，所以只要找最後一個非葉節點($\lfloor \frac{n}{2} \rfloor - 1$)的位置，再往上處理即可。

> The following code is saved in `sorted.c`.

```c=
// heap sort
void heapify(int arr[], int root, int n){
    /** rearrange the array(0-index) to form a max heap
     * Parameter:
     *     arr: input array
     *     root: index of root
     *     n: array length
     */

    int child = 2 * root + 1; // left node by default
    int rootValue = arr[root];

    while (child < n){
        if ( (child + 1 < n) && (arr[child]  < arr[child + 1])){
            child++;
        }
        if (arr[child] <= rootValue){
            break;
        }
        else {
            arr[root] = arr[child];
            root = child;         // sink down and check next level
            child = 2 * root + 1;
        }
    }
    arr[root] = rootValue;
}

void heapSort(int arr[], int n){
    
    // heapify arr to form max heap
    for (int i = (n-1)/2; i >= 0; i--){
        heapify(arr, i, n);
    }

    for (int j = n-1; j > 0; j--){
        swap(&arr[0], &arr[j]);
        // printArray(arr, n); // if you want to show the procedure, uncomment this line
        heapify(arr, 0, j);
    }
}
```

#### Analysis

* Time complexity
    * Worse/best/average case 的時間複雜度均為 $O(n \log n)$。
* Space complexity
    * 需看實作的過程，如果使用迴圈實現，則空間複雜度為 $O(1)$，但如果 `heapify()` 使用遞迴方式進行，則空間複雜度為 $O(n \log n)$。
* Advantage
    * Unstable
    * In-place


## 排序演算法的極限
以比較和交換兩個動作為主的排序演算法中，假設有 n 個元素的陣列需要排列，則可能的排序情況有 $n!$ 種，以樹狀圖結構的示意圖如下

<img src="https://hackmd.io/_uploads/rJtRyKtr1x.jpg" width=500>


因為有 $n!$ 種可能的排序，所以會有 $n!$ 個葉節點。以高度為 $k$ 的 binary tree 來說，葉節點的個數為 $2^k$，故當葉節點數為 $n!$ 時

$$
n! = 2^k \Rightarrow k = \log_2(n!)
$$

考慮到 0-index 的編號系統，因此樹的高度為 $k+1 = \log_2(n!) + 1$

因次，以比較和交換為主的排序演算法中，最差的時間複雜度為 $O(n \log n)$

## 混合排序
### 1. Tim sort

## 特殊排序
### 1. Bucket sort

容器排序法(bucket sort)又稱為 bin sort ，是一種特殊排序法，能夠在 best case 的情況下做到 $O(n)$ 的時間複雜度。

Step-by-Step：

* 將元素分配到不同的 group/bucket
* 對於每個 group/bucket 內部在進行排序，通常是用 insertion sort，因為此時陣列長度變小
* 最後把所有的 group/bucket 依序合併

在進行分組時，會使用類似長方圖找組距的方式決定每一組的長度，再將元素進行映射，轉換到對應的組別。

> THe following code is saved in `sorted.c`.

```c=
// bucket sort
int getMax(int arr[], int n){
    int max = arr[0];

    for (int i=0; i<n; i++){
        if (arr[i] > max)
            max = arr[i];
    }
    return max;
}
int getMin(int arr[], int n){
    int min = arr[0];

    for (int i=0; i<n; i++){
        if (arr[i] < min)
            min = arr[i];
    }
    return min;
}
void bucketSort(int arr[], int n){
    /** bucket sort
     * Variable:
     *     bucketCount: setup the bucket number ,if the tange between max and
     *                  min is small, then bucketCount can't too large.
     *     buckets: an 2-D array which save all buckets
     *     bucketSize: an 1-D array which save bucket size corresponding to buckets[i]
     */
    int bucketCount = 2;
    int min = getMin(arr, n);
    int max = getMax(arr, n);
    int range = (max - min) / bucketCount;

    int **buckets = (int **) malloc(bucketCount * sizeof(int *));  // each bucket
    int *bucketSize = (int *) calloc(bucketCount, sizeof(int *)); // record each bucket size

    // allocate each bucket size
    for (int i=0; i<bucketCount; i++){
        buckets[i] = (int *) malloc(n * sizeof(int*)); // maximum capacity of each bucket
    }

    // scatter the element to each bucket
    for (int i=0; i<n; i++){
        int index = (arr[i] - min) / range;

        if (index == bucketCount)
            index -= 1;
        buckets[index][bucketSize[index]++] = arr[i];
    }

    // sort each bucket
    for (int i=0; i<bucketCount; i++){
        if (bucketSize[i] > 0)
            insertionSort(buckets[i], bucketSize[i]);
    }

    // merge all bucket
    int index = 0;
    for (int i=0; i<bucketCount; i++){
        for (int j=0; j<bucketSize[i]; j++){
            arr[index++] = buckets[i][j];
        }
        free(buckets[i]);
    }
    free(buckets);
    free(bucketSize);
}
```

#### Analysis

* Worse case: $O(n^2)$
當 bucket 中的元素分佈不均，某個 bucket 拿到所有元素時就會退化成 insertion sort。但複雜度還是依據使用的排序方式為主。

* Best case: $O(n+k)$ or $O(n)$
當 bucket 中的元素均勻分佈

* Space complexity: $O(n+k)$


### 2. Counting sort

計數排序(counting sort) 是一種非比較的排序法，核心思想是計算元素出現的次數進行排序，適合用在輸入數值不大的非負整數陣列中，能夠做到 $O(n)$ 的時間，但需要 $O(n+m)$ 空間，其中 m 是陣列的最大值。


整個過程可以分成 3 個步驟：
<img src="https://hackmd.io/_uploads/rJsXTy-8ke.jpg" width=400>

1. 計算出現次數(頻率)
    * 找到輸入陣列的最大值 m
    * 建立 size = m + 1 的計數陣列 `countArr` 並計算元素出現的次數
2. 計算計數陣列 `countArr` 的累加和(presum)

<img src="https://hackmd.io/_uploads/HJXDTJZL1g.jpg" width=400>

3. 從輸入陣列的末端開始迭代
    * 找 `countArr` 中 index = `inputArr[i]` 的元素
    * `countArr[index] - 1` 的值就是 `inputArr[i]`` 需要放置的位置
    * 更新 `countArr[index]`

> The following code is saved in `sorted.c`.

```c=
// counting sort
void countSort(int arr[], int n){
    int max = getMax(arr, n);

    // compute frequency of each element
    int *countArr = calloc(max + 1, sizeof(arr[0]));
    for (int i = 0; i < n; i++)
        countArr[arr[i]]++;
    
    // compute presum of countArr
    for (int i = 1; i < max + 1; i++)
        countArr[i] += countArr[i-1];
    
    // sort from last to beginning
    int *sortedArr = malloc(sizeof(arr[0])*n);
    for (int i = n - 1; i >= 0; i--)
        sortedArr[--countArr[arr[i]]] = arr[i];
    
    // copy to original array
    for (int i = 0; i < n; i++)
        arr[i] = sortedArr[i];
    
    free(countArr);
    free(sortedArr);
}
```

### 3. Key-based sort
想像 array 中的元素有多個鍵值 $K^1$, $K^2$, $K^n$可以做排序。以撲克牌為例有分為花色跟點數兩種鍵值

* 鍵值 $K^1$(花色)：♠️ > ♥️ > ♦️ > ♣️
* 鍵值 $K^2$(點數)：1 > 2 > ... > 13

依據鍵值(key)的重要性進行排序可分為兩種：最重要位優先(Most-Significant-Digit-First, MSD)與最不重要位優先(Least-Significant-Digits-First, LSD)

假設 key 的重要性從 $K^1$ 開始依序遞減，以上述撲克牌為例，對於 MSD 來說：

* 先根據 $K^1$ 的值排序成四堆
* 每堆中再依據 $K^2$ 的值排序

對於 LSD 來說：

* 先依據 $K^2$ 的值分成 13 堆
* 再依據 $K^1$ 的值使用 stable 的排序法分成四堆
* 最後將每堆結果合併

:::info
不論是 MSD 還是 LSD 都只是描述鍵值的順序，不會涉及排序。
:::

### 4. Radix sort

基數排序(radix sort)也是一種 key-based 的排序方法，藉由比較每個位數(digit)來達到線性的複雜度。適合用在固定長度的整數(integer)或字串(string)等資料的排序。

因為是多鍵值的排序方法，所以可以依據鍵值的重要性分為 LSD 與 MSD。

假設輸入陣列如下，因為最大數字有三位(digit=3)，所以必須迭代三次才能排序完成。

$$
[170,\ 45,\ 75,\ 90,\ 802,\ 84,\ 2,\ 66]
$$

根據個位數(digit=1)的排序結果為：

$$
[17 \underline0,\ 9 \underline0,\ 80 \underline2,\ \underline2,\ 2 \underline4,\ 4 \underline5,\ 7 \underline5,\ 6 \underline6]
$$

再根據十位數(digit=2)的排序結果為：

$$
[8 \underline02,\ 2,\ \underline24,\ \underline45,\ \underline66,\ 1 \underline70,\ \underline75,\ \underline90]
$$

最後一句百位數(digit=3)的排序結果為：

$$
[2,\ 24,\ 45,\ 66,\ 75,\ 90,\ \underline170,\ \underline802]
$$

在每一個 digit 排序的過程中，原則上可以使用任何的排序演算法，只要保證 stability 即可，不過習慣上會使用 counting sort 進行。


> The following code is saved in `sorted.c`.

```c=
// radix sort
void sortedDigit(int arr[], int n, int digit){
    
    // compute frequency
    int *countArr = calloc(10, sizeof(arr[0])); // digit from 0 to 9
    for (int i = 0; i < n; i++)
        countArr[(arr[i] / digit) % 10]++;
    
    // conpute presum
    for (int i = 1; i < 10; i++)
        countArr[i] += countArr[i-1];
    
    // sort
    int *sortedArr = malloc(n * sizeof(arr[0]));
    for (int i = n - 1; i >= 0; i--)
        sortedArr[--countArr[(arr[i] / digit) % 10]] = arr[i];
    
    // copy to original array
    for (int i = 0; i < n; i++)
        arr[i] = sortedArr[i];
    
    free(countArr);
    free(sortedArr);
}

void radixSort(int arr[], int n){
    int max = getMax(arr, n);

    for (int digit = 1; max / digit > 0; digit *= 10){
        sortedDigit(arr, n, digit);
        /** printArray(arr, n);
         * if want to show sorting process
         * uncomment this line 
         */
    }
}
```

## Reference

* [Rust Algorithm CLub](https://rust-algo.club/index.html)
* [GeeksforGeeks](https://www.geeksforgeeks.org)

## Interview Ques.

### 1. Quick sort
```c=
#include <stdio.h>

void swap(int *, int *);

void quickSort(int, int, int []);

int main(void) {
    int arr[] = {1, 5, 4, 3, 2};
    int n = sizeof(arr) / sizeof(int);
    
    quickSort(0, n-1, arr);
    
    printf("arr = ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int left, int right, int arr[]) {
    if (left >= right) {
        return;
    }
    
    int mid = (left + right) / 2;
    int pivot = arr[mid];
    int L = left;
    int R = right;
    
    while (L <= R) {
        // find smaller than pivot
        while (arr[L] < pivot) {
            L++;
        }
        // find greater than pivot
        while (arr[R] > pivot) {
            R--;
        }
        if (L <= R) {
            swap(&arr[L], &arr[R]);
            L++;
            R--;
        }
    }
    quickSort(left, R, arr);
    quickSort(L, right, arr);
}
```
