項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【演算法筆記 #3】QuickSort 重點整理筆記,包含 Partition, Pivot 常見錯誤討論 #重要題型

前言

QuickSort 算是面試中或是演算法中經典的問題,非常重要,
而且最容易搞錯「他的範圍」,因此這邊來將自己的常見錯誤做一個總整理。

先一個正式版本

基本上,要講出 QuickSort 的核心精神,人人幾乎都不太會犯錯,
但程式非常容易寫錯,特別是在區間的控制過程。

QuickSort 的核心精神

QuickSort 的核心精神就是選定一個 pivot (可以頭可以尾),
將剩下的數字透過 pivot 分成 「 < pivot 」 與 「 > pivot 」 兩組。

最容易出錯的地方 – 決定邊界

在撰寫程式的時候,如果沒有仔細思考,或甚至已經仔細思考了都還經常會寫錯。

注意:這邊示範的並「不是」主流的教科書寫法,而是用釐清觀念候「用自己的方式」寫的。

我們的目的如上圖,就是希望在循環結束時,能夠

  • 讓 left 左邊的一切都是 smaller (than pivot)
  • 讓 right 右邊的一切都是 bigger (than pivot)

因此 (以下為說明用的程式碼,並不完整)

while(left <= right):
    while(left <= right and a[left] < pivot):
        left += 1
    while(left <= right and a[right] > pivot):
        right -= 1
    if left <= right:
        a[left], a[right] = a[right], a[left]

注意啦! 光上面這裡有很多細節了!

left <= right

首先是 left <= right,如果寫 left < right 達不到交錯的效果,有可能出迴圈要多做處理

不是不能這樣寫,就是要多做一些處理,沒有什麼不能的寫法

a[left] < pivot, a[right] > pivot

注意這裡不處理等於,原因是處理等於也不一定好,
等於表示與 pivot 相等,用於處理重複的 array,
但如果硬要處理等於的情況,在 [1,1,1,1,1] 類似這樣的 case,
一定會用 worst case 的 O(n) 時間去解,而不是平均的 O(nlogN)。

可以先理解 QuickSort 的 worst case 是什麼情況及為什麼會發生,
這樣更能夠懂為什麼會舉到上面的例子。

此種類的完整的 QuickSort 程式碼

    def partition(self, nums, start, end):
        # recusion end
        if start >= end:
            return 

        # recursion define
        left, right = start+1, end
        pivot = nums[start]

        while(left <= right):
            while(left <= right and nums[left] < pivot):
                left += 1
            while(left <= right and nums[right] > pivot):
                right -= 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
        else:
            nums[start], nums[right] = nums[right], nums[start]

        print(nums, left, right)

        # recursion split
        self.partition(nums, start, right-1)
        self.partition(nums, left, end)

抓 partition 與 pivot 的重點

我們設計的思想是

  • 一開始:
    pivot(start) < (left, start+1) < (right, end)

  • 結束時,交換前 (注意交錯):

(start) < start+1 < right < left < end

務必注意交錯的位置的「 right < left 」,這是最最重要的部分。

  • 結束時,交換後 (注意交錯):

start < right-1 < pivot(right) < left < end

而 start ~ right-1 都比 pivot 小
left < end 都比 pivot 大。

結束迴圈 recursion 「start >= end」

不論是

  • self.partition(nums, start, right-1)
  • self.partition(nums, left, end)

right 會越來越逼近 start,直到重疊 start >= end
而 left 也會越來越逼近 end (因為 left 與 right 是交錯,只會更逼近 end)

另外一種寫法

建議先嘗試閱讀以下程式碼,思考一下
(這我寫過的東西,我也想了很久為什麼)

while(left <= right)
    if a[left] < pivot:
        left += 1
    elif a[right] > pivot:
        right -= 1
    else:
        a[left], a[right] = a[right], a[left]
        # left += 1
        # right -= 1

建議想好後再看,這樣才會更印象深刻。

注意 left <= right

一樣要注意的 left <= right,因為一定要交錯。

「left += 1」、「right -= 1」可有可無

其中「left += 1」、「right -= 1」可有可無,
沒有當下處理也會在之後的迴圈被處理掉。

此種類的完整的 QuickSort 程式碼

def partition(self, nums, start, end):
        # recusion end
        if start >= end:
            return 

        # recursion define
        left, right = start+1, end
        pivot = nums[start]

        while(left <= right):
            if nums[left] < pivot:
                left += 1 
            elif nums[right] > pivot:
                right -= 1 
            else:
                nums[left], n