[演算法] 學習筆記 — 12. 快速排序法 Quick Sort

Amber Fragments

10 min readNov 29, 2022

特性

跟 Merge Sort 一樣，Quick Sort 也是利用了同樣的概念：「當一個陣列只有 0 或 1 的元素的時候，它必定已經是排好序的。」

做法

Quick Sort 與 Merge Sort 雖然利用同樣的概念，但是作法上差異很大，它會先從陣列中選擇一個「樞紐」（pivot），然後將所有小於樞紐的值都移到它的左邊、將所有大於樞紐的值都移到它的右邊。移動的過程我們並沒有去做排序，我們只是先將它們移到某一邊。
ps. 結束時，只有 pivot 會在它最後正確的位置上（也就是只有樞紐是在排好序的位置）。
當樞紐完成以後，我們對左半部分再次進行同樣的處理（找到 pivot、移動位置），再處理右半部分。

例子

舉個例，如果我們現在有一組陣列，我們先選擇一個值做為 Pivot，這邊先選擇第一個 5，然後將所有比 5 小的數都移到 5 的左邊：

source: JavaScript Algorithms and Data Structures Masterclass，以下相同

當全部移動完後應該會像這樣：

接著，我們用同樣的方法處理左半部分，選擇第一個值 3 作為 Pivot，將所有比 3 小的值移到 3 的左邊，比 3 大的留在 3 的右邊：

移動完成的時候是這樣：

接著，3 的左半部分還有 2 個數字（還不是「只有 0 或 1 個元素」），所以我們繼續選擇第一個值 1 作為 Pivot，移動比它小的值：

而 2 大於 1，因此我們不動，最後剩下 2 一個元素，不需要再移動了。此時陣列的左半部分就完成了排序。

接著以同樣的步驟我們處理右半部分，選擇右邊的第一個值作為 Pivot，將比 7 小的元素移到 7 的左邊：

這時，在右半部分，7 的左邊和右邊都只剩下一個元素了：

這時，我們就完成了這個陣列的排序！

Pivot Helper Function

跟 Merge Sort 很像的是，在寫出完整的的排序演算法之前，我們要先來寫它的輔助用的函式，在 Quick Sort 是 Pivot Helper。

Pivot Helper 要做的事情就是在陣列中選擇一個元素作為 Pivot，然後遍歷整個陣列，將比 Pivot 小的元素移到左邊，比 Pivot 大的元素留在右邊。而移過去後的元素順序沒關係，我們不需要去排序它，我們只要知道左邊的元素都比 Pivot 小，右邊的元素都比 Pivot 大，這樣就可以了。

很重要的是，在輔助函式中，我們是直接去改變陣列中元素的位置，而不是另外創造一個新陣列！（這會影響空間複雜度）

當 Pivot Function 跑完以後，它應該回傳 Pivot 最後的位置（index）。

如何選擇 Pivot

Quick Sort 的處理速度部分取決於我們如何選擇 Pivot。

理想上，我們應該要選擇陣列最中間的元素作為 Pivot，這樣 Pivot 左邊的元素數量與右邊的元素素量會相等或接近相等。

在這邊，為了方便教學，Colt 會選擇第一個元素作為 Pivot。

Pivot Helper Function 的虛擬碼

一如以往，我們先來寫輔助函式的虛擬碼。

Pivot 函式接受 3 個 input：一個陣列、起始的 index、最後的 index。起始 index 可以給予預設值 0 ，最後 index 給予預設值 -1。

（補充一下，陣列有個 method: “array.at(-1)”，是取出陣列的最後一個元素，可以用來替換 arr[arr.length - 1] 的寫法）

function pivot(arr, start = 0, end = arr.length - 1) {
    // ...
}

選擇陣列的第一個元素作為 Pivot。
建立一個變數，並將我們選擇的 pivot index 記錄起來，這是為了去追蹤 pivot 的位置，讓我們之後可以執行 swap。
遍歷陣列，如果發現比 pivot 小的元素（假定是 x ），這時我們將 pivot index + 1，然後將 x 與「pivot index + 1 的元素」交換位置（swap）。
當這一輪的遍歷完成後，我們將 pivot 與「pivot index + 1 的元素」再進行 swap！

（可以理解為什麼 Colt 說他的大腦有點排斥 Quick Sort 了，的確是有點不直覺的步驟🥹）

Pivot Helper Function

實際寫起來的 Pivot helper function 是這樣：

function pivot(arr, start = 0, end = arr.length - 1) {

    function swap(array, i, j) {    // 這邊我們先將會用到的 swap 函式作為 helper function 寫出來
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }


    let pivot = arr[start]
    let swapIdx = start

    for (let i = start + 1; i < arr.length; i++) {
        if (pivot > arr[i]) {
            swapIdx++
            swap(arr, swapIdx, i)
        }
    }
    swap(arr, start, swapIdx)
    return swapIdx
}

Quick Sort 的虛擬碼

在動手寫虛擬碼之前，首先我們知道：pivot helper function 回傳的是每一次 pivot 最後所在的位置。

因此我們要做的是，遞迴地呼叫 pivot helper function，讓它處理「index 0 ～前一次回傳的 swapIdx」的元素、以及「swapIdx ～陣列最後」的元素（也就是 swapIdx 的左半部分和 swapIdx 的右半部分）。

Pseudo Code 的部分如下：

對 input 的陣列呼叫 pivot function 。
當 pivot function 回傳了最後的 pivot index 後，我們再次呼叫 pivot function，function 的 start 以及 end 分別是「start = 0, end = pivot index」以及「start = pivot index, end = array.length - 1」
持續上面的流程直到當 pivor index 的左半和右半部分都只剩下 0 或 1 個元素。

Quick Sort

這邊可以注意的是 base case，我們要停止遞迴的條件。我們希望在 pivot index 的左半或右半部分「只剩下 0 或 1 個元素的時候」不再執行 pivot function，這個條件怎麼寫呢？

因為每次的 arr 都是不變的，都是最一開始 input 的陣列，也就是完整的陣列，所以這邊不能用 arr.length 去做判斷條件。

但是這邊 left 和 right 是持續在變動的，當我們要處理的那一小段 subarray 長度越來越短的時候，left 與 right 就會越來越靠近，當 left 與 right 相等的時候，就代表這段 subarray 已經只有 1 個元素了。

因此在這邊我們的 base case 就是 left = right，換作條件判斷式則是：
「當 left < right 的時候，我們持續呼叫 pivot function」。

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left < right) {
        let pivotIndex = pivot(arr, left, right)

        // left
        quickSort(arr, left, pivotIndex - 1)

        // right
        quickSort(arr, pivotIndex + 1, right)
    }

    return arr
}