Quick Sort

tags: 演算法 資料結構

HackMD Error: 404 error

• Quick Sort
• 課堂作業
• 課外資料
  • 簡介
  • 特點
  • 複雜度分析
  • Is QuickSort stable?
  • Is QuickSort In-place?
  • 參考網站
• Quick-Sort by linked-List
  • 參考網站

課堂作業

老師的範例_array

老師的範例_linked-List

課外資料

簡介

Quick Sort 他是以 divide-and-conquer 演算法為基礎。他的概念其實很簡單，就是從 array 中抽取一個數字為 pivot（基準點），將整個 array 依基準點分成兩個小的 array, 比基準點大的放在右邊的array，比基準點小的放在左邊的array，之後左右兩邊的小array 繼續重複同樣到動作（找基準->分兩邊）直到該小array剩下一個為未排序（未當過基準點）。

他有四種方式

• 總是以第一個 element 為基準點
• 總是以最後一個 element 為基準點
• 以中位數為基準點
• 隨機基準點(下圖)

特點

• 他有回歸性 (recursive)
• 屬於分治法 (divide-and-conquer)
• 有效率的處理大的資料

複雜度分析

• 時間複雜度

  • 最差: [ Big-O ]: O(n2)

  • 理想: [Big-omega]: O(n*log n)

  • 平均: [Big-theta]: O(n*log n)

• 空間複雜度: O(n*log n)

Is QuickSort stable?

其實由上面的時間複雜度就可以知道 QuickSort 是一個不穩定的排序方式。它的表現跟基準點的選擇有關，當你排序後所有element 都在基準點的同一側，也就是說你選擇的基準點在 array 裡是最大或最小的值，

Is QuickSort In-place?

In-place: 原地演算法

廣義來看 QuickSort 也算是原地演算法，一個原地演算法（in-place algorithm）基本上不需要額外輔助的資料結構,但允許少量額外的輔助變數來轉換資料的演算法。

參考網站

• https://www.hackerearth.com/zh/practice/algorithms/sorting/quick–sort/tutorial/
• https://www.geeksforgeeks.org/quick-sort/
• https://www.studytonight.com/data-structures/quick-sort
• https://www.youtube.com/watch?v=CB_NCoxzQnk

Quick-Sort by linked-List

參考網站

https://www.geeksforgeeks.org/quicksort-on-singly-linked-list/