Sorting algorithm - Quicksort

Quicksort堪稱最知名實用性又高的排序演算法，操作方式稍微比較複雜一點：先從數列中隨機選取一個基準值(pivot)，通常會直接選用數列最末值，或是隨機選取後再將pivot放在數列最末端，接著由左至右和pivot作比較，凡是比pivot小的值就依序放在左側，直到做完一輪就可將數列區分為{<pivot, pivot, >pivot}，即決定了pivot所在的最終位置，然後再按照此方式繼續處理被分割的小區塊直到結束。此演算法又被稱之為partition-exchange sort。

Quicksort algorithm

由於其分割簡化數列長度的概念降低了系統運行的複雜度，因此可用更有效率的方式完成排序，是較為實用的選擇，底下這段影片也許就是最好的證明。

<Complexity performance>

• Worst case: O(n²) 
• Best case: O(n*logn) 
• Average case: O(n*logn)

影片的最後有一段Bubble sort與Quicksort間的競賽，好奇誰會獲勝嗎？

---

<參考資料來源>
Wikipedia - Quicksort