# [資料結構] CH15. Heap and Shell Sorts & Comparisons

* 把最後兩個排序法講完。

## Heap Sort
* 堆排序法和Binary Tree Sort有點像，我們要建一顆complete binary tree來幫助我們排序。
* Heap Tree分為兩種：
* Min Heap: 每個node的值一定比自己小孩還要**小**。
* Max Heap: 每個node的值一定比自己小孩還要**大**。
* node可以等於小孩的值。

digraph HeapTree{
subgraph cluster_level1
{
    label = "Min Heap"
	1 [label="4"];
	2 [label="20"];
	3 [label="66"];
	4 [label="22"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

subgraph cluster_level2
{
    label = "Max Heap"
	B1 [label="100"];
	B2 [label="20"];
	B3 [label="66"];
	B4 [label="1"];
    B5 [label="16"];
    B6 [label="40"];
    B7 [label="45"];

	B1 -> B2
	B1 -> B3
    B2 -> B4
    B2 -> B5
    B3 -> B6
    B3 -> B7
}
}

* 示意圖：
* 

### 插入
* 要在一棵Heap Tree插入一筆新的資料很簡單，只有兩個步驟：
1. 將資料新增至Tree的底部。
2. 和父親比較值，依情況交換。
* 範例：插入`19`。

digraph HeapTree{
    label = "Min Heap"
	1 [label="4"];
	2 [label="20"];
	3 [label="66"];
	4 [label="22"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

* 先將`19`放置於底部。

digraph HeapTree{
    label = "Min Heap"
	1 [label="4"];
	2 [label="20"];
	3 [label="66"];
	4 [label="22"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];
    8 [label="19"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
}

* 與父親比較，發現`19`<`22`，交換。

digraph HeapTree{
    label = "Min Heap"
	1 [label="4"];
	2 [label="20"];
	3 [label="66"];
	4 [label="19"color ="red"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];
    8 [label="22" color ="red"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
}

* 再次與父親比較，發現`19`<`20`，交換。

digraph HeapTree{
    label = "Min Heap"
	1 [label="4"];
	2 [label="19"color ="red"];
	3 [label="66"];
	4 [label="20"color ="red"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];
    8 [label="22" ];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
}

* 再次與父親比較，發現`19`>`4`，完成。

### 刪除
* Heap Tree的刪除**永遠從root刪除**。
* 因為很重要我要再說一次，**永遠從root刪除**。
* 刪除的步驟分為以下三個：
1. 將root與最後加入的node交換。
2. 刪除被換到最下面的root node。
3. 將被換到最上面的node與其小孩比較，依情況交換，直到滿足Heap Tree的特性。
* 範例：進行刪除一次。

digraph HeapTree{
	1 [label="4"];
	2 [label="19"];
	3 [label="66"];
	4 [label="20"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];
    8 [label="22" ];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
}

* 先將root和`22`交換。

digraph HeapTree{
	1 [label="22"color="red"];
	2 [label="19"];
	3 [label="66"];
	4 [label="20"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];
    8 [label="4"color="red"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
    4 -> 8
}

* 刪除被移到下面的root。

digraph HeapTree{
	1 [label="22"];
	2 [label="19"];
	3 [label="66"];
	4 [label="20"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

* 將被移到上面的node與小孩比較，發現`22`>`19`，交換。

digraph HeapTree{
	1 [label="19"color="red"];
	2 [label="22"color="red"];
	3 [label="66"];
	4 [label="20"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

* 繼續比較，發現`22`>`20`，交換。

digraph HeapTree{
	1 [label="19"];
	2 [label="20"color="red"];
	3 [label="66"];
	4 [label="22"color="red"];
    5 [label="67"];
    6 [label="99"];
    7 [label="101"];

	1 -> 2
	1 -> 3
    2 -> 4
    2 -> 5
    3 -> 6
    3 -> 7
}

* `22`已經沒有小孩可以比較了，完成刪除。

### 排序
* 我們已經教完如何建立一顆Heap Tree了，那到底如何排序呢？
* 給予一個陣列Arr，使用Heap Sort的步驟為兩步：
1. 建立Heap Tree。
2. 不停刪除直到樹沒有任何node。
* 由於Heap Tree的刪除只會從root，且root永遠為最大/最小值，便可以完成排序。

## Shell Sort
* 希爾排序法屬於**插入排序法**的改良版，是一種不穩定的排序法。
* 觀察插入排序法可以發現兩件事情：
1. 插入排序法對於幾乎已經排好的資料有非常高的效率。
2. 但大多數的時候效率不高，因為一次只將資料移動一位。
* 因此Shell Sort將資料先分堆，再進行Insertion sort，以提高效率。
* 示意圖：分堆步長為`23` `10` `4` `1`的Shell Sort。
* 
### Gaps
* Shell Sort需要先分堆，每堆到底有幾筆資料我們稱為步長(Gap)。
* 這個Gap到底要怎麼使用，我們來看個範例比較快理解：
* 範例：Gap = 8, 5, 1 ，使用Shell Sort排序陣列`A`。
* `A` = {`63`,`19`,`7`,`90`,`81`,`36`,`54`,`45`,`72`,`27`,`22`,`9`,`41`,`59`,`33`}
#### 第一次排序
* 第一次排序先每堆`8`個，所以總共有兩堆(為了方便對齊，統一用兩個數字表示)：
* `63`,`19`,`07`,`90`,`81`,`36`,`54`,`45`
* `72`,`27`,`22`,`09`,`41`,`59`,`33`
* 每一堆的第n個數做Insertion Sort，結果為：
* `63`,`19`,`07`,`09`,`41`,`36`,`33`,`45`
* `72`,`27`,`22`,`90`,`81`,`59`,`54`
* 因此現在的陣列為：
* `A` = {`63`,`19`,`07`,`09`,`41`,`36`,`33`,`45`,`72`,`27`,`22`,`90`,`81`,`59`,`54`}
#### 第二次排序
* 第一次排序先每堆`5`個，所以總共有三堆：
* `63`,`19`,`07`,`09`,`41`
* `36`,`33`,`45`,`72`,`27`
* `22`,`90`,`81`,`59`,`54`
* 每一堆的第n個數做Insertion Sort，結果為：
* `22`,`19`,`07`,`09`,`27`
* `36`,`33`,`45`,`59`,`41`
* `63`,`90`,`81`,`72`,`54`
* 因此現在的陣列為：
* `A` = {`22`,`19`,`07`,`09`,`27`,`36`,`33`,`45`,`59`,`41`,`63`,`90`,`81`,`72`,`54`}
#### 最後排序
* 最後一次排序的gap一定要設為`1`。
* gap為`1`的Shell Sort其實就是Insertion Sort。
* 但由於前面已經分堆整理過了，因此排序速度會加速。
---
* 若gap只有`1`，此時Shell Sort 完全等於 Insertion Sort。
* gap要取多少比較好？
* 不一定。

## 各排序法分析
* Bubble Sort:
* Average/Best/Worst Case: $𝐎(𝑛^2)$
* 無論怎樣都要跑完雙層for loop。
* Insertion Sort:
* Best Case: $𝐎(𝑛)$
* Worst Case: $𝐎(𝑛^2)$
* 如果已經排完的資料，只需跑一次for loop用於檢查。
* 完全相反的資料，每一筆資料都要跑一次for loop，所以一樣為雙層。
* Selection Sort:
* Average/Best/Worst Case: $𝐎(𝑛^2)$
* 與Bubble Sort一樣，無論怎樣都會跑完雙層for loop。
* Merge Sort:
* Average/Best/Worst Case: $𝐎(nlogn)$
* 雖然十分穩定與快速，但需要額外空間。
* Quick Sort:
* Best Case: $𝐎(nlogn)$
* Worst Case: $𝐎(𝑛^2)$
* 如果每次pivot都切在中間就是最好情形。
* 每次都切在頭或尾巴就是最糟情形。
* Radix Sort:
* Best Case: $𝐎(k𝑛)$
* Worst Case: $𝐎(𝑛^2)$
* k為有幾位數字。
* Shell Sort:
* Best Case: ?
* Worst Case: $𝐎(𝑛^2)$
* 不穩定的排序，不知道最好有多好，且取決於你的gap怎麼設定。
* 最糟和Insertion Sort一樣。
* Heap Sort:
* Average/Best/Worst Case: $𝐎(nlogn)$
* 必定為Balance Tree。
* Tree Sort:
* Best Case: $𝐎(nlogn)$
* Worst Case: $𝐎(𝑛^2)$
* 最好是Balance Tree的情形。
* 最糟是歪斜樹的情形。

## 其他資源
* 蠻有趣的排序法影片，YT上有蠻多類似的東西，可以幫助了解各種排序法的特性等等。
{%youtube kPRA0W1kECg %}

###### tags: `DS` `note`