# 【資工考研】DSA: Search and Sort
## Search
1. Linear (sequential) search
2. Binary search
### Linear Search
適合在支援 random access (e.g. array) 或 sequential access (e.g. linked list) 的資料結構上實作
Time complexity: $O(n)$
```cpp!
template <typename T>
int linearSearch(const std::vector<T> &arr, T x)
{
if (arr.empty())
return -1;
const int n = arr.size();
for (int i = 0; i < n; ++i)
{
if (arr[i] == x)
return i;
}
return -1;
}
```
```cpp!
template <typename T>
int sentinelSearch(std::vector<T> &arr, T x)
{
if (arr.empty())
return -1;
const int n = arr.size();
T last = arr.back();
if (last == x)
return n - 1;
arr.back() = x;
int i = 0;
while (arr[i] != x)
++i;
arr.back() = last;
return i < n - 1 ? i : -1;
}
```
### Binary Search
1. **資料需要事先排序過**
2. 資料必須保存在支援 random access 的資料結構上
Time complexity: $O(\lg n)$
想法：Divide and Conquer
每次都找出當前區段 (\[`l`, `r`]) 最中間位置 (`mid`) 的資料做比對
如果不是所要資料，因為資料已經保證為有序的，故如果位於 `mid` 的資料比目標小，表示目標在 `mid` 右邊 (\[`mid + 1`, `r` ])；如果位於 `mid` 的資料比目標大，表示目標在 `mid` 左邊 (\[`l`, `mid - 1` ])
不斷對半切，縮小搜尋範圍，最終找到目標
```cpp!
template <typename T>
int binarySearch(const std::vector<T> &arr, T x)
{
int l = 0, r = arr.size() - 1;
while (l <= r)
{
const int mid = l + (r - l) / 2; // mid = (l + r) / 2
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
l = mid + 1;
else
r = mid - 1;
}
return -1;
}
```
遞迴寫法：
```cpp!
template <typename T>
int binarySearch(const std::vector<T> &arr, T x, int l = 0, int r = -1)
{
if (r == -1)
r = arr.size() - 1;
if (l > r)
return -1;
const int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
return binarySearch(arr, x, mid + 1, r);
return binarySearch(arr, x, l, mid - 1);
}
```
從遞迴寫法我們可以很容易看出時間函數為 $T(n) = T(\frac{n}{2}) + 1 = O(\lg n)$
||$n$ 筆資料以 BST 找 `x` |$n$ 筆資料以 Binary search 找 `x`|
|:---:|:---:|:---:|
| Best Case | $O(\lg n)$ | $O(1)$ |
| Worst Case | $O(n)$ | $O(\lg n)$ |
## Sort
|| Time Complexity | Time Complexity | Time Complexity | Space Complexity | Stable |
|:---:|:---:|:---:|:---:|:---:|:---:|
| Method | Best Case | Worst Case | Avg. Case | | |
| Insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | O |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | X |
| Bubble | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | O |
| Shell | $O(n)$ | $O(n^\frac{23}{15})$ | $O(n^2)$ | $O(1)$ | X |
| Quick | $O(n\lg n)$ | $O(n^2)$ | $O(n\lg n)$ | $O(\lg n)$ to $O(n)$ | X |
| Merge | $O(n\lg n)$ | $O(n\lg n)$ | $O(n\lg n)$ | $O(n)$ | O |
| Heap | $O(n\lg n)$ | $O(n\lg n)$ | $O(n\lg n)$ | $O(1)$ | X |
### Insertion Sort
想法：
我們從第二個元素 ($\mathrm{arr}\lbrack 1 \rbrack$) 開始看到最後一個 ($\mathrm{arr}\lbrack n-1 \rbrack$)
對於 $\mathrm{arr}\lbrack i \rbrack$ ，其前 $i-1$ 筆資料都**已經是**排序好的
我就找到 $\mathrm{arr}\lbrack 0\cdots i-1 \rbrack$ 中哪裡插入 $\mathrm{arr}\lbrack i \rbrack$ 會使 $\mathrm{arr}\lbrack 0\cdots i \rbrack$ 為有序即可
例如
> input: `[5, 3, 6, 2, 4]`
$i = 1$: `[3, 5, 6, 2, 4]`
$i = 2$: `[3, 5, 6, 2, 4]`
$i = 3$: `[2, 3, 5, 6, 4]`
$i = 4$: `[2, 3, 4, 5, 6]`
```cpp!
template <typename T, typename Compare = std::less<T>>
void insertionSort(std::vector<T> &arr)
{
const int n = arr.size();
Compare comp;
for (int i = 1; i < n; ++i)
{
T key = arr[i]; // element to be inserted
int j = i - 1;
while (j >= 0 && comp(key, arr[j])) // arr[j] > key
{
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
```
我們預設是由小排到大的升序排列
Time Complexity:
- Best case: $O(n)$ ，當 input 是由小到大 ($T(n) = T(n-1) + 1 = O(n)$)
- Worst case: $O(n^2)$ ，當 input 是由大到小 ($T(n) = T(n-1) + n-1 = O(n^2)$)
- Avg. case: $O(n^2)$ ($T(n) = T(n-1) + \frac{1+\cdots +n-1}{n-1} = O(n^2)$)
Space Complexity:
無須額外空間，故 $O(1)$
Stable:
最簡單的檢驗方式就是有兩個一樣的值出現在 `arr` 時，排序過後會不會改變這兩個值原本輸入時的先後順序
例如 `[2, 5, 5*, 3]`
你會發現 insertion sort 要抓取 `5*` 時(`key = 5*`) 他是找在 `5*` 之前有沒有比它還大的，而 `5` 並沒有比它大
所以不會改變先後順序
我們可以這樣設計資料
```cpp!
struct Data
{
int key;
char label;
friend bool operator<(const Data &lhs, const Data &rhs) noexcept
{
return lhs.key < rhs.key;
}
};
```
```cpp!
int main()
{
std::vector<Data> arr = {
{2, '\0'},
{5, '\0'},
{5, '*'},
{3, '\0'},
};
insertionSort(arr);
printData(arr);
}
```
最後結果 `[2, 3, 5, 5*]`
insertion sort 很適合資料少時使用
### Selection Sort
想法：
$i$ 從頭看到倒數第二個
對於區間 $\mathrm{arr}\lbrack i\cdots n \rbrack$ 找出其最小值 $\mathrm{arr}\lbrack min \rbrack$ 並 $\mathrm{swap}\left( \mathrm{arr}\lbrack i \rbrack, \mathrm{arr}\lbrack min \rbrack \right)$
例如
> input: `[5, 3, 6, 2, 4]`
$i=0$: `[2, 3, 6, 5, 4]`
$i=1$: `[2, 3, 6, 5, 4]`
$i=2$: `[2, 3, 4, 5, 6]`
$i=3$: `[2, 3, 4, 5, 6]`
$i=4$: `[2, 3, 4, 5, 6]`
```cpp!
template <typename T, typename Compare = std::less<T>>
void selectionSort(std::vector<T> &arr)
{
const int n = arr.size();
Compare comp;
for (int i = 0; i < n - 1; ++i)
{
int min = i;
for (int j = i; j < n; ++j)
{
// find the pos of min
if (comp(arr[j], arr[min])) // arr[j] < arr[min]
min = j;
}
if (i != min)
std::swap(arr[i], arr[min]);
}
}
```
Time Complexity:
都是 $O(n^2)$
Space Complexity:
$O(1)$
可以注意到，selection sort 的特點就是 $i$ 的迭代過程中每回合頂多只會 swap 一次
對於大型紀錄之排序，該一特點能展現出來
不過 selection sort 是 unstable 的
```cpp!
int main()
{
std::vector<Data> arr = {
{2, '\0'},
{5, '\0'},
{5, '*'},
{3, '\0'},
};
selectionSort(arr);
printData(arr);
}
```
結果： `[2, 3, 5*, 5]`
這是因為我們每次只在意小的值有沒有放到正確的位置上，並沒有在意 swap 過程中造成的先後順序打亂
### Bubble Sort
想法：
由左而右兩相鄰元素互比
如果前者大於後者則 swap
> [!Tip]
> 最多只會有 $n-1$ 回合，每個回合我們都會把極大值升到最後面去
> [!Note]
> 如果改成從右到左操作，那就是把極小值降到最前面去
```cpp!
template <typename T, typename Compare = std::less<T>>
void bubbleSort(std::vector<T> &arr)
{
const int n = arr.size();
Compare comp;
for (int i = 0; i < n - 1; ++i)
{
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j)
{
// if (arr[j] > arr[j + 1])
if (comp(arr[j + 1], arr[j]))
{
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) // no swap, stop iteration
break;
}
}
```
Time Complexity:
- Best Case: $O(n)$ ，當資料是由小到大排好 ($T(n) = n-1 = O(n)$)
- Worst Case: $O(n^2)$ ，當資料由大到小排好 ($T(n) = T(n-1) + n -1 = O(n^2)$)
- Avg. Case: $O(n^2)$ ($T(n) = T(n-1) + O(n) = O(n^2)$)
Space Complexity:
$O(1)$
Bubble sort 是 stable 的
因為我們是從前看到後，每次比大小，一樣的兩個值，在前面的不會被 swap 到後面去
```cpp!
int main()
{
std::vector<Data> arr = {
{2, '\0'},
{5, '\0'},
{5, '*'},
{3, '\0'},
};
bubbleSort(arr);
printData(arr);
}
```
最後結果 `[2, 3, 5, 5*]`
### Shell Sort
Shell sort，也是一種 in-place 的比較排序演算法
它可以被理解為 bubble sort 或 insertion sort 的泛化
這個方法的開始是將相距較遠的元素成對排序，然後逐步減少要比較的元素之間的間隔
通過從遠距離的元素開始，它可以比單純的鄰近交換更快地將某些錯位的元素移到正確的位置
Shellsort 的運行時間非常依賴於它使用的間隔序列 (gap sequence)
對於許多實用的變體，其時間複雜度的確定仍然是未解的問題
考試不怎麼考它
就算考也不太可能考你它的時間複雜度，正如上面講的，這不是什麼很基礎的問題
以下為 [wiki](https://en.wikipedia.org/wiki/Shellsort#Pseudocode) 上的 pseudocode
```pseudocode!
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1] # Ciura gap sequence
# Start with the largest gap and work down to a gap of 1
# similar to insertion sort but instead of 1, gap is being used in each step
foreach (gap in gaps)
{
# Do a gapped insertion sort for every element in gaps
# Each loop leaves a[0..gap-1] in gapped order
for (i = gap; i < n; i += 1)
{
# save a[i] in temp and make a hole at position i
temp = a[i]
# shift earlier gap-sorted elements up until the correct location for a[i] is found
for (j = i; (j >= gap) && (a[j - gap] > temp); j -= gap)
{
a[j] = a[j - gap]
}
# put temp (the original a[i]) in its correct location
a[j] = temp
}
}
```
### Quick Sort
想法：也是 Divide and Conquer
選擇一個元素作為 pivot ，決定其正確位置使得位於 pivot 左邊的資料都 $\le$它、位於 pivot 右邊的資料都 $\ge$ 它
這樣的方式就把原始陣列拆兩邊了，再對兩邊也進行 quick sort
#### Hoare's partition
我們每次都挑最左邊的當作 pivot 並且用以下方式進行 partition：
`[pv, _, _, _, _, _, _, _, _, _]`
兩個指標 `i` 跟 `j` 分別從左右兩側開始選，他們分別代表到時候 pivot 的左右兩邊
他們的目標是要挑出不符合我們目標 「位於 pivot 左邊的資料都 $\le$它、位於 pivot 右邊的資料都 $\ge$ 它」 的元素
`[pv, _, i, _, _, _, _, _, _, j]`
每次找到後就 $\mathrm{swap}\left( \mathrm{arr}\lbrack i \rbrack , \mathrm{arr}\lbrack j \rbrack \right)$
(`i` 跟 `j` 找到的分別是對方那邊需要的元素， swap 後相對排序就正確了)
之後當 `i` 超過 `j` 時表示該結束了
`[pv, _, _, _, _, j, i, _, _, _]`
結束的最後一步是 $\mathrm{swap}\left( \mathrm{arr}\lbrack l \rbrack , \mathrm{arr}\lbrack j \rbrack \right)$
其中 $\mathrm{arr}\lbrack l \rbrack$ 即 pivot
這樣就的確達成 「位於 pivot 左邊的資料都 $\le$它、位於 pivot 右邊的資料都 $\ge$ 它」
```cpp!
template <typename T, typename Compare>
int partition(std::vector<T> &arr, int l, int r, Compare comp)
{
T pivot = arr[l];
int i = l, j = r + 1;
while (true)
{
do
{
++i;
} while (i <= r && comp(arr[i], pivot)); // arr[i] < pivot
// stop when arr[i] >= pivot
do
{
--j;
} while (j >= l && comp(pivot, arr[j])); // arr[j] > pivot
// stop when arr[j] <= pivot
if (i >= j)
break;
std::swap(arr[i], arr[j]);
}
std::swap(arr[l], arr[j]);
return j;
}
template <typename T, typename Compare = std::less<T>>
void quickSort(std::vector<T> &arr, int l = 0, int r = -1)
{
if (r == -1)
r = arr.size() - 1;
if (l < r)
{
Compare comp;
int p = partition(arr, l, r, comp);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
}
```
最後我們再對 pivot 兩邊也 quick sort 即可
Time Complexity:
- Best Case: $(n\lg n)$ ，如果資料皆相同 or pivot 恰好將資料分成兩等分 ($T(n) = 2T(\frac{n}{2}) + O(n)$)
- Worst Case: $O(n^2)$ ，如果資料是由小到大或由大到小 (pivot 會選成最小或最大值) ($T(n) = T(n-1) + O(n^2)$)
- Avg. Case: $O(n\lg n)$ ($T(n) = \frac{1}{n}\left\lbrack\sum\limits_{i=0}^{n-1} T(i) + T(n-i-1) \right\rbrack + n -1$)
可以看到， pivot 選的如何影響了 quick sort 的表現
Space Complexity:
因為我們需要遞迴呼叫，所以是 $O(\lg n)$ 到 $O(n)$
Quick sort 很明顯，是 unstable 的
```cpp!
int main()
{
std::vector<Data> arr = {
{5, '*'},
{5, '\0'},
{5, '\0'},
{5, '\0'},
{5, '\0'},
};
quickSort(arr);
printData(arr);
}
```
結果： `[5, 5, 5*, 5, 5]`
#### Comen's Partition
只差在怎麼寫 partition
```cpp!
template <typename T, typename Compare>
int partition(std::vector<T> &arr, int l, int r, Compare comp)
{
T pivot = arr[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j)
{
if (!comp(pivot, arr[j])) // arr[j] <= pivot
std::swap(arr[++i], arr[j]);
}
std::swap(arr[++i], arr[r]);
return i;
}
```
之後就都一樣
```cpp!
template <typename T, typename Compare = std::less<T>>
void quickSort(std::vector<T> &arr, int l = 0, int r = -1)
{
if (r == -1)
r = arr.size() - 1;
if (l < r)
{
Compare comp;
int p = partition(arr, l, r, comp);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
}
```
這個版本反而會有個問題，那就是當資料都相同時，反而變成 worst case $O(n^2)$
解決辦法有兩種：
1. 先檢查是不是資料都相同，雖然要花 $O(n)$ 來檢查，但時間複雜度上還是不影響
2. 改用 Hoare 提出的 partition
#### Median of Medians
我們說過，怎麼選 pivot 會影響 quick sort 的表現
我們就算亂數隨機挑一個當 pivot ，worst case 也還是一樣 $O(n^2)$
好的挑法例如 middle of three 或是 median of medians
以下介紹 median of medians 的想法：
1. 我們先將資料分成 $\left\lceil \frac{n}{5} \right\rceil$ 組，每組盡量塞滿 $5$ 個元素
2. 每組各自做排序，因為資料量很小，可以用 insertion sort 使這步驟維持在 $O(n)$
3. 將這 $\left\lceil \frac{n}{5} \right\rceil$ 組中的中位數組成一個集合，再從該集合中挑選中位數作為 pivot ，此即 median of medians (標題回收)
4.
```cpp!
template <typename Iterator, typename Compare = std::less<typename std::iterator_traits<Iterator>::value_type>>
void insertionSort(Iterator first, Iterator last, Compare comp = Compare())
.
.
.
template <typename T, typename Compare>
int partition(std::vector<T> &arr, int l, int r, Compare comp)
{
const int n = r - l + 1;
if (n <= 5)
{
insertionSort(arr.begin() + l, arr.begin() + r + 1, comp);
return l + n / 2;
}
const int numGroups = (n + 4) / 5; // ⌈ n/5 ⌉
for (int i = 0; i < numGroups; ++i)
{
const int start = l + i * 5;
const int end = std::min(start + 4, r);
insertionSort(arr.begin() + start, arr.begin() + end + 1, comp);
std::swap(arr[l + i], arr[start + (end - start) / 2]);
}
const int idx = l + numGroups / 2;
insertionSort(arr.begin() + l, arr.begin() + l + numGroups, comp);
T pivot = arr[idx];
// Just like we did before.
int i = l, j = r + 1;
while (true)
{
do
{
++i;
} while (i <= r && comp(arr[i], pivot));
do
{
--j;
} while (j >= l && comp(pivot, arr[j]));
if (i >= j)
break;
std::swap(arr[i], arr[j]);
}
std::swap(arr[l], arr[j]);
return j;
}
template <typename T, typename Compare = std::less<T>>
void quickSort(std::vector<T> &arr, int l = 0, int r = -1)
{
if (r == -1)
r = arr.size() - 1;
if (l < r)
{
Compare comp;
int p = partition(arr, l, r, comp);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
}
```
這樣就保證 quick sort worst case 也是 $O(n\lg n)$
> [!Important]
> 像這些 comparison-based 的想法，一般時間最快達 $\Omega (n\lg n)$
### Merge Sort
想法：Divide and Conquer
比較兩個數，小的擺前面，這樣的問題應該簡單到不行吧？
資料量不大的時，比較大小排順序對我們不是什麼很難的問題
Merge sort 的想法便是把原始資料拆到足夠小，小到我們很容易解決
再把結果合併回來，得出所求
```cpp!
template <typename T, typename Compare>
void merge(std::vector<T> &arr, int l, int mid, int r, Compare comp)
{
const int n1 = mid - l + 1;
const int n2 = r - mid;
std::vector<T> arrL(arr.begin() + l, arr.begin() + mid + 1); // arr[l ... mid]
std::vector<T> arrR(arr.begin() + mid + 1, arr.begin() + r + 1); // arr[mid + 1 ... r]
int i = 0, j = 0, k = l;
while (i < n1 && j < n2)
{
if (comp(arrR[j], arrL[i])) // arrL[i] > arrR[j]
arr[k++] = arrR[j++];
else
arr[k++] = arrL[i++];
}
while (i < n1)
arr[k++] = arrL[i++];
while (j < n2)
arr[k++] = arrR[j++];
}
template <typename T, typename Compare = std::less<T>>
void mergeSort(std::vector<T> &arr, int l = 0, int r = -1)
{
Compare comp;
if (r == -1)
r = arr.size() - 1;
if (l < r)
{
const int mid = l + (r - l) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r, comp);
}
}
```
Time Complexity:
都是 $O(n\lg n)$
Space Complexity:
merge sort 並非 in-place 的
我們需要額外的空間先處理完子問題，最後才合併
需要 $O(n)$
Merge sort 是 stable 的
```cpp!
int main()
{
std::vector<Data> arr = {
{2, '\0'},
{5, '\0'},
{5, '*'},
{3, '\0'},
};
mergeSort(arr);
printData(arr);
}
```
結果： `[2, 3, 5, 5*]`
> [!Important]
> 任何 stable 的 sorting algorithm 寫的時候都要注意等號的處理！
> 寫錯就會失去 stable
### Heap Sort
建立 [heap](https://hackmd.io/@RyoukiWei/binary_tree_1#Heap) 來排序
```cpp!
template <typename T, typename Compare>
void heapify(std::vector<T> &arr, int n, int i, Compare comp)
{
int largest = i;
const int left = 2 * i + 1;
const int right = 2 * i + 2;
if (left < n && comp(arr[largest], arr[left]))
largest = left;
if (right < n && comp(arr[largest], arr[right]))
largest = right;
if (largest != i)
{
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest, comp);
}
}
template <typename T, typename Compare = std::less<T>>
void heapSort(std::vector<T> &arr)
{
const int n = arr.size();
Compare comp;
// Build a max heap
for (int i = n / 2 - 1; i >= 0; --i)
{
heapify(arr, n, i, comp);
}
// Extract elements one by one from the heap
for (int i = n - 1; i > 0; --i)
{
std::swap(arr[0], arr[i]); // Move the largest element to the end
heapify(arr, i, 0, comp); // Restore the heap property
}
}
```
Time Complexity:
都是 $O(n\lg n)$
> [!Tip]
> 做 $n-1$ 回合類似 $\mathrm{delete-max}$ 的操作，每回合 $O(\lg n)$
> 故總共 $O(n\lg n)$
Space Complexity:
直接拿原陣列操作，所以是 in-place 的，$O(1)$
那很顯然 heap sort is unstable
### Counting Sort
Counting sort 並不是用 comparison 的方式
它適用於我們對當前資料的值域是已知的情況
這種時候我們可以用找數字的方式來排順序
```cpp!
template <typename T, typename Key, typename Functor>
void countingSort(const std::vector<T> &arr, std::vector<T> &output, Key k, Functor getKey)
{
std::vector<Key> freq(k + 1);
for (const auto &entry : arr)
{
++freq[getKey(entry)];
}
for (int i = 1; i <= k; ++i)
{
freq[i] += freq[i - 1];
}
const int n = arr.size();
output.resize(n);
for (int i = n - 1; i >= 0; --i)
{
output[freq[getKey(arr[i])]--] = arr[i];
}
}
template <typename T, typename Key>
void countingSort(const std::vector<T> &arr, std::vector<T> &output, Key k)
{
std::vector<Key> freq(k + 1);
for (const auto &entry : arr)
{
++freq[entry];
}
for (int i = 1; i <= k; ++i)
{
freq[i] += freq[i - 1];
}
const int n = arr.size();
output.resize(n);
for (int i = n - 1; i >= 0; --i)
{
output[freq[arr[i]]--] = arr[i];
}
}
```
Time Complexity:
都是 $O(n+k)$
因為 $k$ 其實是已知的常數，所以 counting sort 是 linear time algorithm
Space Complexity:
$O(n+k)$
而可想而知，我們抓數字時，相同的值是按照原本陣列的順序在抓的
所以是 stable 的
Sign in with Wallet
Connect another wallet