【資工考研】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)$

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;
}

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 ])

不斷對半切，縮小搜尋範圍，最終找到目標

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;
}

遞迴寫法：

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}[1]$) 開始看到最後一個 (

$\mathrm{arr}[n-1]$)
對於

$\mathrm{arr}[i]$ ，其前

$i-1$ 筆資料都已經是排序好的
我就找到

$\mathrm{arr}[0\cdots i-1]$ 中哪裡插入

$\mathrm{arr}[i]$ 會使

$\mathrm{arr}[0\cdots i]$ 為有序即可

例如

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]

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 並沒有比它大
所以不會改變先後順序

我們可以這樣設計資料

struct Data
{
    int key;
    char label;

    friend bool operator<(const Data &lhs, const Data &rhs) noexcept
    {
        return lhs.key < rhs.key;
    }
};

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}[i\cdots n]$ 找出其最小值

$\mathrm{arr}[min]$ 並

$\mathrm{swap}(\mathrm{arr}[i],\mathrm{arr}[min])$

例如

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]

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 的

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

如果改成從右到左操作，那就是把極小值降到最前面去

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 到後面去

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 上的 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}(\mathrm{arr}[i],\mathrm{arr}[j])$
(i 跟 j 找到的分別是對方那邊需要的元素， swap 後相對排序就正確了)

之後當 i 超過 j 時表示該結束了

[pv, _, _, _, _, j, i, _, _, _]

結束的最後一步是

$\mathrm{swap}(\mathrm{arr}[l],\mathrm{arr}[j])$
其中

$\mathrm{arr}[l]$ 即 pivot

這樣就的確達成 「位於 pivot 左邊的資料都

$\le$它、位於 pivot 右邊的資料都

$\ge$ 它」

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}[\sum _{i=0}^{n-1}T(i)+T(n-i-1)]+n-1$)

可以看到， pivot 選的如何影響了 quick sort 的表現

Space Complexity:

因為我們需要遞迴呼叫，所以是

$O(\lg n)$ 到

$O(n)$

Quick sort 很明顯，是 unstable 的

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

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;
}

之後就都一樣

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. 我們先將資料分成
   $\lceil \frac{n}{5}\rceil$ 組，每組盡量塞滿
   $5$ 個元素
2. 每組各自做排序，因為資料量很小，可以用 insertion sort 使這步驟維持在
   $O(n)$
3. 將這
   $\lceil \frac{n}{5}\rceil$ 組中的中位數組成一個集合，再從該集合中挑選中位數作為 pivot ，此即 median of medians (標題回收)

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 的想法，一般時間最快達

$\mathrm{\Omega }(n\lg n)$

Merge Sort

想法：Divide and Conquer

比較兩個數，小的擺前面，這樣的問題應該簡單到不行吧？
資料量不大的時，比較大小排順序對我們不是什麼很難的問題

Merge sort 的想法便是把原始資料拆到足夠小，小到我們很容易解決
再把結果合併回來，得出所求

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 的

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 來排序

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 的方式
它適用於我們對當前資料的值域是已知的情況

這種時候我們可以用找數字的方式來排順序

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 的