淺談Divide And Conquer

Day12有提到Divide and conquer(分治法)，簡單的說，將問題分解為小問題後，依次解決，最後再將解決後的問題組合起來。今天要提到的快速排序法也是Divide and conquer的其中一種方法。

快速排序(Quick Sort)

快速排序是從數列中隨機選擇一個數作為基準(Pivot)，接著將剩下的數字分為比Pivot小或比Pivot大的值

(比Pivot小的數) Pivot (比Pivot大的數)

快速排序有使用到Divide and conquer，將原問題分成兩個子問題（比Pivot大或小），再分別解決兩個子問題。各自排序後，重新將子問題的數列排列，就能得到結果。
解決子問題後，同樣使用Quick Sort，直到子問題剩下一個數時，排序結束。在過程中會使用到recursion的概念。

import random

#從1-100中隨機讀取8個數字
nums = random.sample(range(1,100), 8)
print(nums)

# nums = [60,50,44,82,55,47,99,33]

def quicksort(L, R):
    #當L<R表示還有兩個以上的元素需要排列
    if(L < R):
        #i初始化變數為L
        i=L
        #j初始化變數為R+1
        j=R+1
        while(1):
            #變數i不斷遞增直到找出nums[i]>nums[L]的元素，或i>R就停止
            i=i+1
            while((i < R) and (nums[i] < nums[L])):
                i=i+1
            #變數j不斷遞減直到找出nums[j]<nums[L]的元素，或j小於L就停止
            j=j-1
            while((j>L) and (nums[j]>nums[L])):
                j=j-1
            #當i>=j就停止迴圈
            if(i >= j):break
            nums[i],nums[j] = nums[j], nums[i]   
        nums[L],nums[j] = nums[j],nums[L]
        print("L=", L, " j=", j, " R=", R)
        for item in nums:
            print(item, ' ',end='')
        quicksort(L, j-1)
        quicksort(j+1, R)

for item in nums:
    print(item, ' ',end='')
print()
quicksort(0,7)

let arr = [15, 3, 17, -17, 3.1415, 18, 20, 2, 1, 666];
quickSort(0, arr.length - 1);
console.log(arr);

function partition(p, r) {
  let x = arr[r]; // pivot
  let i = p - 1;
  for (let j = p; j <= r - 1; j++) {
    if (arr[j] <= x) {
      i += 1;
      // swap arr[i] and arr[j]
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  // swap arr[i+1] and arr[r]
  let temp = arr[i + 1];
  arr[i + 1] = arr[r];
  arr[r] = temp;

  return i + 1;
}

function quickSort(p, r) {
  if (p < r) {
    let q = partition(p, r);
    quickSort(p, q - 1);
    quickSort(q + 1, r);
  }
}

結論

快速排序法的平均效率為O(n log(n))，相較於氣泡排序或插入排序的效能較佳，但最差情況的時間為O(n^2)，每次切割時都很不平均，相較於合併排序法，合併排序的最差情況比快速排序法佳。