Sorting Algorithm

tags: algo sorting python

前言

在計算機科學中，排序演算法指的是將一串資料依照特定排序方式進行排列的演算法，常見的排列方式有數值順序與字典順序。而排序演算法的輸出必須遵守下列兩個原則：

1. 輸出結果為遞增(或遞減，依照所需的排列方式)序列
2. 輸出結果必須是原輸入的一種排列或是重組

排序演算法是一個簡單易懂的問題，同時也非常的重要，在許多的系統中，排序演算法往往佔了整體執行時間的絕大部分，特別在處理大量資料的排序時，選擇適合的排序演算法，將能夠大大的提升整體系統的執行效能。

那麼要如何評估一個排序演算法呢？就必須先了解甚麼是演算法的時間複雜度。

時間複雜度（Time Complixity）

一個演算法的時間複雜度是一個函數，描述該演算法輸入資料的長度與執行時間的關係。我們通常用 \(O\) 來表示這個函數，並且不包括首項以外的低階項及首項係數。定義如下：

If \(\exists c,k \in \mathbb{R} : |f(x)|\le c|g(x)|\) where \(x \gt k,\) then \(f(x)\) is \(O(g(x))\)

\(x\) 表示演算法輸入的資料個數，\(O(g(x))\) 表示該演算法的時間複雜度。由定義可以看出，時間複雜度 \(O\) 看的是執行時間隨資料規模增長的變化趨勢，而不是真正的執行時間。會這樣表示的原因是因為我們只考慮當資料量非常大的時候，執行時間函式的低階項將變得可以忽略。

常見的排序演算法

• Bubble Sort
• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort
• Heap Sort
• Counting Sort
• Radix Sort

Bubble Sort

Bubble Sort 的排序方法為從頭開始，相鄰的數兩兩比較並交換，總共需要比較 \((n-1) + (n-2) + ... + 1 = {n^2 - n \over 2}\) 次才能確定排序結束，因此時間複雜度為 \(O(n^2)\)。
雖然 Bubble Sort 在大多數的時候相較於其他的排序演算法慢，但也有適用的時機。在使用 SSE2 (又稱 SIMD)指令集時，如果能使用 GPU 運算，改良過的 Bubble Sort 可以因為 Vector Computing 的特性而加速，資料量小且可利用 GPU 運算時，可以考慮使用。

Iterative Bubble Sort

def bubbleSort(nums):
    l = len(nums)
    for i in range(1, l):
        for j in range(0, l-1):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

Recursive Bubble Sort

def bubbleSortRecursive(isSorted, step):
    global nums
    if (step == 1) or isSorted:
        # if sorted or swap (n -1) times, return
        return nums
    else:
        isSwapped = False
        for i in range (len(nums) - 1):
            if nums[i] > nums[i + 1]:
                isSwapped = True
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
        # if swapped, check again
        return bubbleSortRecursive(not isSwapped, step - 1)

Insertion Sort

Insertion Sort 會將數列分成已排序好與未排序好兩個部分，每一次都從未排序好的數列選出第一個數，從已排序好的左或右開始，依序檢視直到所比較的數比未排序好的第一個數大或小，此時將為排序好的第一個數插入到這個位置上，直到未排序的數列長度為 0。
由於 Insertion Sort 在最差的情況下每個數都需要與所有已排序好的數做比較，因此總共比較的次數為 \(0 + 1 + ... + (n-1) = {n^2 - n \over 2}\) 次，時間複雜度為 \(O(n^2)\)。
Insertion Sort 的特性為每次插入都會搬移所有比較過的數，因此 Insertion Sort 較適合小資量 (<100) 的排序，或者是幾乎以排序好的情況。同時，資料整排搬移的特性也很適合 Vector Computing。
Quick Sort 在 Partition 進入到小資料量時，轉換成 Insertion Sort 能對 Quick Sort 有一定的加速效果。

Iterative Insertion Sort

def insertionSort(nums):
    for i in range (1, len(nums)):
        # i 是要插入的數 將值存在 key
        key = nums[i]
        # j 表示當前比較的值
        j = i - 1
        # 如果 j 還沒到底 且 j 上面的值比 key 大 則 一路上的值全部往右移
        while j >= 0 and key < nums[j]:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = key
    return nums

Recursive Insertion Sort

def insertionSort(nums, n):
    if n <= 1:
        return
    # Sort first n-1 elements
    insertionSort(nums, n - 1)
    last = nums[n - 1]
    j = n - 2
    while (j >= 0 and nums[j] > last):
        nums[j + 1] = nums[j]
        j = j - 1
        swap_time += 1
    nums[j + 1] = last
    return nums

Selection Sort

Selection Sort 與 Insertion Sort 很像，同樣會將數列分成未排序好與已排序好兩部分，差別在於，Selection Sort 每次從未排序好的數列中找出最大或最小的數，放到以排序好的數列最後，直到未排序好的數列長度為 0。
與 Insertion Sort 相同，每次選出最大最小數的過程，就需要和所有為排序的數做比較，因此比較次數為 \((n-1) + (n-2) + ... + 0 = {n^2 - n \over 2}\)，時間複雜度為 \(O(n^2)\)
Selection Sort 的最大特性為交換的次數最少，這使得在如果排序的資料本身做交換的運算需要付出很大代價的時候，例如：Swap 就重畫 window、Swap 數百 MB 的資料等等，將可以考慮使用 Selectiion Sort。但資料量不夠多時，交換次數少所帶來的優勢將會被抵銷掉。

Iterative Selection Sort

def selectionSort(nums):
    for i in range (len(nums)):
        MinNum = nums[i]
        MinIdx = i
        for j in range(i + 1, len(nums)):
            if MinNum > nums[j]:
                MinNum = nums[j]
                MinIdx = j
        nums[i], nums[MinIdx] = nums[MinIdx], nums[i]
    return nums

Recursive Selection Sort

def minIndex(nums , i , j):    
    Min = nums[i]
    Min_idx  = i
    for n in range (i + 1, j + 1):
        if a[n] < Min:
            Min = nums[n]
            Min_idx = n
    return Min_idx

def selectionSort(nums, n, index = 0):
    if index == n:
        return -1
    k = minIndex(nums, index, n-1)
    if k != index:
        nums[k], nums[index] = nums[index], nums[k]
    selectionSort(nums, n, index + 1)
    return nums

Quick Sort

Quick Sort 屬於 Devide and Conquer 的一種排序方法。Quick Sort 主要由兩個步驟組成：Partition 與 Sort。Partition 的內容為隨機從要處理的數列中取出一個數作為 Pivot(通常會選最右或最左的數)，Sort 則讓其他的每一個數都和這個 Pivot 比較大小，小的數會放到 Pivot 的左邊，而比 Pivot 大的數則會放到 Pivot 的右邊，並在左右兩個子數列中再重複 Partition 與 Sort 直到分割出來的子數列的長度 \(\le2\) (直接兩個數比大小)，即完成排序。
Quick Sort 不斷分割的過程會讓處理的數列個數不斷減少，在最佳的情況下，每一次 Partition 所選到的 Pivot 皆為該數列的中位數，此時每一次分割的子數列長度都會是原本數列長度的\({1 \over 2}\)，而每次比較的次數為數列長度，因此總共比較次數為 \(n\) \(+\) \({1 \over 2}n*2\) \(+\) \({1 \over 4}n*4\) \(+\) \(...\) \(+\) \({1 \over n}n*n\) \(= n\log_{2}{n}\)，所以時間複雜度為 \(O(n\log_{}{n})\)；但如果是最差的情況，即每次 Partition 所選到的 Pivot 皆為所處理數列的最大或最小值，則每一次 Partition 其實就處理了一個數，剩餘的 \(n-1\) 個數仍然未排序，比較的次數就變為 \((n-1) + ... +1 = {n^2 - n \over 2}\) 次，時間複雜度為 \(O(n^2)\)。
由此可知，Pivot 的選擇將很大程度的影響 Quick Sort 排序速度，在以最左或最右的數做為 Pivot 的挑選策略下，幾乎已排序或反向排序的數列將非常不適合使用 Quick Sort。另外，Quick Sort 的排序結果為 Unstable 結果，意思是如果數列中出現了一對相同的數字，由 Quick Sort 排序好的數列順序並不保證這兩個相同的數字會依照在原本數列中出現的順序。

Iterative Quick Sort

def partition(arr, l, h):
    i = (l - 1)
    pivot = arr[h]
    for j in range(l, h):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i] 
    arr[i + 1], arr[h] = arr[h], arr[i + 1]
    return (i + 1)

def quickSort(arr, l, h):
    size = h - l + 1
    stack = [0] * (size)
    
    # 一次放入一組子數列的左右區間到 stack 裡
    top = -1
    top = top + 1
    stack[top] = l
    top = top + 1
    stack[top] = h
    
    while top >= 0:
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1
        
        pivot = partition( arr, l, h )
        
        if pivot - 1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = pivot - 1
 
        if pivot + 1 < h:
            top = top + 1
            stack[top] = pivot + 1
            top = top + 1
            stack[top] = h
    return arr

Recursive Quick Sort

def partition(arr, left, right):
    i = left - 1
    pivot = arr[right]
    for j in range(left, right):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return (i + 1)

def quickSort(arr, left, right):
    if len(arr) == 1:
        return arr
    if left < right:
        pi = partition(arr, left, right)
        quickSort(arr, left, pi - 1)
        quickSort(arr, pi + 1, right)
    return arr

Quick Sort 補充說明

• Average case : \(O(nlogn)\)

• Pivot 的選擇
  由前面的介紹可以知道，Pivot 的選擇會很大程度的影響 Quick Sort，那麼使用好的 Pivot 選擇策略就能改善這個問題，當然前提是選擇 Pivot 的方法時間複雜度不能高於排序本身。
  首先，第一種方法為 Median-of-3，顧名思義就是選擇三個隨機的數並取中間的數作為 Pivot，如此就能避免所選到的數為最大或最小，同時實作簡單，增加的額外運算也少並且改善的程度高，在許多預設的排序方法使用 Quick Sort 的程式語言中都使用了這樣的改善。
  第二種方法稱為 Median-of-medians。如果想要每一次都最佳化分割的結果，代表每一次的 Pivot 選擇都必須選到要處理數列的中位數。詳細演算法的內容寫在這篇 The Median-of-Medians Algorithm。

• Multi-pivot Quick Sort
  那麼除了改善選擇 Pivot 的策略，如果再多加幾個 Pivot 呢？事實上，增加 Pivot 數量，在好的 Pivot 選擇策略下(例如 : Median-of-3)，只會讓比較次數與交換次數變得更多。但是，在實驗上，2-pivot 的 Quick Sort 卻比 1-pivot 的 Quick Sort 執行更快，甚至 3-pivot 也有如此的現象。而 Java 內建的排序方法在 Java 7 版本之後，也由原本的 1-pivot Quick Sort 改為 Yaroslavskiy 所提出的 2-pivot Quick Sort。造成這樣的原因是當 Pivot 數少的時候 Partition 也相對比較大，在 Cache Size 相同的情況下，1-pivot 的 Quick Sort 發生了較多次的 Cache Miss。這導致了多個 Pivot 即使比較次數更多卻執行得更快的現象。Multi-pivot Quick Sort。

Yaroslavskiy's Dual-pivot Quick Sort

def partition(arr, left, right):
    if arr[left] > arr[right]:
        arr[left], arr[right] = arr[right], arr[left]
    lp = left
    rp = right
    j = k = left + 1
    g, p, q = right - 1, arr[lp], arr[rp]

    # k遍歷, g代表大於arr[rp]的邊界, j代表小於arr[lp]的邊界
    while k <= g:
        if arr[k] < p:
            arr[k], arr[j] = arr[j], arr[k]
            j += 1
        elif arr[k] >= q:
            while k < g and arr[g] > q:
                g-=1
            arr[k], arr[g] = arr[g], arr[k]
            g -= 1
            if arr[k] < p:
                arr[k], arr[j] = arr[j], arr[k]
                j += 1
        k += 1
    j -= 1
    g += 1
    
    arr[lp], arr[j] = arr[j], arr[lp]
    arr[rp], arr[g] = arr[g], arr[rp]
    swap_time += 2
    
    return j, g

def quickSort2pivot(arr, left, right):
    if left < right:
        lp, rp = partition(arr, left, right)
        quickSort2pivot(arr, left, lp - 1)
        quickSort2pivot(arr, lp + 1, rp - 1)
        quickSort2pivot(arr, rp + 1, right)
    return arr

Merge Sort

Merge Sort 也是屬於 Devide and Conquer 的一種排序方法。Merge Sort 實作的方法可以分成 Top-down 與 Bottom-up 兩種。
Top-down 的作法是將數列不斷二分成兩個子數列直到個數剩下 \(1\)。接著鄰近的兩個數列開始合併成排序好的數列，再與另外一組合併好的數列再次合併，直到全部的數都合併完成。
Bottom-up 的作法則是直接從頭開始兩個數兩個數合併，合併完成的數列再和鄰近合併完成的數列再次合併。直到數列剩下一個。
Top-down 和 Bottom-up 兩個方法其實差異不大，主要是在實作時寫法的不同，Top-down 通常用遞迴的方式寫，Bottom-up 用迭代的方式寫。兩種方法當中，合併的過程都為取兩個欲合併數列，用兩個 Pointer 指向兩個數列的第一個數並做比較，將兩者之中較小或較大的那個數放進已合併的數列的後方，將該數列的指標往後移一個，直到其中一邊的指標最後一個元素的後面，則將另外一邊剩餘的數依序放入以排序數列的後方，即完成一次合併。

Merge Sort 範例

Merge Sort 排序可以保證 Stable 的結果，同時，合併的過程其實也可以多個數列合併成一個，另外，Merge Sort 的方式可以實現外部排序（External Sort），即資料量極大而記憶體一定不夠的時候，須借用外部儲存空間來完成排序。每次只從外部空間取記憶體足夠的資料量來排序再放回。

Iterative Merge Sort

def merge(arr, temp, frm, mid, to):
    # k 合併的index
    k = frm 
    # i, j 左右子數的index
    i = frm
    j = mid + 1
    while i <= mid and j <= to:
        if arr[i] < arr[j]:
            temp[k] = arr[i]
            i = i + 1
        else:
            temp[k] = arr[j]
            j = j + 1
        k = k + 1
    while i < len(arr) and i <= mid:
        temp[k] = arr[i]
        k = k + 1
        i = i + 1
    for i in range(frm, to + 1):
        arr[i] = temp[i]
 
def mergeSort(nums):
    low = 0
    high = len(nums) - 1
    temp = nums.copy()

    # m 表示要合併區間大小
    m = 1
    while m <= high - low:
        for i in range(low, high, 2*m):
            frm = i
            mid = i + m - 1
            to = min(i + 2*m - 1, high)
            merge(nums, temp, frm, mid, to)
        m = 2*m
    return nums

Recursive Merge Sort

def merge(left, right):
    sortData = []
    leftIdx, rightIdx = 0, 0
    for i in range(0, (len(left) + len(right))):
        if leftIdx == len(left):
            sortData.append(right[rightIdx])
            rightIdx += 1
        elif rightIdx == len(right):
            sortData.append(left[leftIdx])
            leftIdx += 1
        elif left[leftIdx] <= right[rightIdx]:
            sortData.append(left[leftIdx])
            leftIdx += 1
        elif right[rightIdx] < left[leftIdx]:
            sortData.append(right[rightIdx])
            rightIdx += 1
    return sortData

def mergeSort(nums):
    if len(nums) > 1:
        lef = mergeSort(nums[0:(len(nums)//2)])
        rig = mergeSort(nums[(len(nums)//2):])
        result = merge(lef, rig)
        return result
    else:
        return nums

Heap Sort

Heap Sort 透過建立 Max Heap or Min Heap 並維持 Heap 的結構來完成排序。在剛開始時，會先將數列中所有的數依序放入 Heap 中，接著透過每一個父節點與其子節點比較並交換的方式，建立 Max Heap or Min Heap。建立好 Max Heap or Min Heap 之後，Root 的節點即代表了數列中的最大值或最小值。此時，將 Root 的數和最後一個節點的數交換，並讓 Heap 的長度 \(-1\)，代表將最大或最小值放到最後面，並在之後的 Heap Sort 中只需要排序剩下的 \((n-1)\) 個數。從 Root 開始，如果發生父節點與子節點交換的情況，就再檢查子節點為 Root 的子樹是否也是一個 Max Heap or Min Heap，直到沒有發生交換為止。重複將 Root 換到最後並重新建立 Max Heap or Min Heap 的這個過程，直到 Heap 內沒有數即完成排序。

Heap Sort 範例

Heap Sort 利用 Heap 來快速找到數列中最大或最小數的特性，非常適合不需要全部排序而只需要最大或最小前幾項的應用。
但 Heap Sort 不適合結果要求必須 Stable 的情況。

Iterative Heap Sort

def buildMaxHeap(arr, n):
    for i in range(n):
        # 如果子節點比較大
        if arr[i] > arr[int((i - 1) / 2)]:
            j = i
            # 交換直到父節點比較大
            while arr[j] > arr[int((j - 1) / 2)]:
                arr[j], arr[int((j - 1) / 2)] = arr[int((j - 1) / 2)], arr[j]
                j = int((j - 1) / 2)
  
def heapSort(arr):
    n = len(arr)
    buildMaxHeap(arr, n) 
    for i in range(n - 1, 0, -1):
        # 交換最後節點與 root
        arr[0], arr[i] = arr[i], arr[0]
        j, index = 0, 0
        while True:
            # 先把指標放在左節點
            index = 2 * j + 1
             
            # 如果右節點比較大才指向右節點
            if (index < (i - 1) and arr[index] < arr[index + 1]): 
                index += 1
          
            # 比較指標與父節點 
            if index < i and arr[j] < arr[index]: 
                arr[j], arr[index] = arr[index], arr[j]
            # 檢查子樹
            j = index 
            if index >= i:
                break    
    return arr

Recursive Heap Sort

def heapify(arr, n, i):
    # 父點先設為最大
    largest = i

    # 算左右子點idx
    l = 2 * i + 1
    r = 2 * i + 2     

    # 檢查有沒有左右子點 且 有沒有比 arr[i] 大
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r

    # 有的話交換，子樹建 maxheap
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    
    # n // 2 ~ 0 代表所有會有子節點的點，所以只需要全部都做過 heapify 就可以得到 maxheap
    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    # 每次都交換最大值與最後一個點再排除掉最後一個點
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

    return arr

Counting Sort

Counting Sort 提供了排序的一種新的想法。想像數列中出現的數字種類是一個一個的桶子，當我們檢視數列時，就把看到的數字放到對應的桶子裡，全部掃過一遍之後，再從最小或最大的桶子開始依序拿出數字，如此一來當我們把桶子裡的數字都拿出來時，數列也就排序好了。這類的排序方法我們稱為桶排序。
桶排序擺脫了數值本身大小的比較，也不需要制定繁雜的分割處理方法，同時時間複雜度在適合的情況下變得更低。但當然，缺點也就是桶排序的使用時機相對的限縮。首先，以 Counting Sort 來說，只適合使用在純數值的情況，並且具備全距，還要全距必須遠小於排序個數，否則就會消耗太多記憶體空間。

Iterative Counting Sort

def countingSort(nums):
    MaxNum = max(nums)
    MinNum = min(nums)
    output = [0 for i in range (len(nums))]
    interval = MaxNum - MinNum + 1
    count = [0 for i in range (interval)]
    
    # shift to 0~interval 
    for i in range (len(nums)):
        count[nums[i] - MinNum] += 1

    # accumulate
    for i in range (1, interval):
        count[i] += count[i-1]
    
    # 將遇到的數字放到該數字出現的區間最後一位，再將區間-1
    for i in range (len(nums)):
        output[count[nums[i] - MinNum] - 1] = nums[i]
        count[nums[i] - MinNum] -= 1
    return output

Recursive Counting Sort

def countingSort(nums):
    global MinNum, count
    if (len(nums) == 1):
        count[nums[0] - MinNum] += 1
    else:
        mid = len(nums) // 2
        countingSort(nums[0:mid])
        countingSort(nums[mid:])
    
    # 只計算 count 後續的輸出不在遞迴內
    return count

Radix Sort

Radix Sort 可以看成是 Counting Sort 的變化，不對數值的的出現次數做統計，而是在每個位數中對 0~9 的數字做統計，並從最低位到最高位(或最高位到最低位)重覆，如此一來一樣能夠排序整個數列。
Radix Sort 算是稍微改善了 Counting Sort 嚴格的使用時機，但也有它自己的限制。首先，Radix Sort 適合排序長度幾乎都一致的資料，例如：身分證字號、郵遞區號等，另外，資料的位數（\(K\)）也必須遠小於排序的個數（\(N\)）才會適合，如果排序資料的位數與個數差不多，Radix Sort 的時間複雜度將會接近糟糕的\(O(N^2)\)。

Iterative Radix Sort

def countingSort(arr, exp):
    output = [0 for i in range (len(arr))]

    # 紀錄該exp的 0~9 出現次數
    count = [0 for i in range (10)]
    for i in range (len(arr)):
        index = arr[i] // exp
        count[index % 10] += 1
    for i in range (1, 10):
        count[i] += count[i - 1]

    # 因為是從數字區間的最後一個開始放，所以上一次排序結果的最大者要先放，因此從後面開始
    i = len(arr) - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    for i in range (len(arr)):
        arr[i] = output[i]

def radixSort(arr):
    MaxNum = max(arr)
    exp = 1
    while MaxNum // exp > 0:
        countingSort(arr, exp)
        exp *= 10
    return arr

Recursive Radix Sort

def countingSort(arr, exp1):
    n = len(arr)
    output = [0] * (n)
    count = [0] * 10
    for i in range(0, n):
        index = arr[i] // exp1
        count[index % 10] += 1
     for i in range(1, 10):
        count[i] += count[i - 1]
    i = n - 1
    while i >= 0:
        index = arr[i] // exp1
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]

def radixSort(arr, maxNum, exp):
    if maxNum // exp > 0:
        countingSort(arr, exp)
        radixSort(arr, maxNum, exp*10)
    return arr

---

參考資料 :
The Median-of-Medians Algorithm