終於來到最後一個 comparison sort algorithm，Quick Sort

Quick Sort

• A sorting method that based on the divide and conquer idea which use partition as a keystep.
• It select a pivot element from the array and rearrange elements so that elements less than pivot come before it, and larger elements comes after it.
• Quick sort is recursively applied to the subarray formed by partitioning after whole dataset is sorted.

What is Partition?

• Partition is not a standalone sorting algorithm; rather, it divides the array into two subarrays.

• The pivot element is placed in its correct position, ensuring that element on one side are smaller and others are larger, but only the pivot is guaranteed to be in the right order at each step.

• Partition 本身並不是排序演算法，它的主要作用是將單一的 array 分割成兩個 subarray

• 從 array 中隨機選一個 element ，稱該 element 為 pivot（選 pivot 有不同種方式，例如：選首項、選末項、選中間項），將小於 pivot 的項目置於左側，大於 pivot 的項目置於右側，最後將 pivot 放在正確的位置

Steps of Quick Sort

Complexity of Quick Sort

O(n logn)

Implementation of Quick Sort

其他資源

Learn Quick Sort in 13 minutes
https://www.youtube.com/watch?v=Vtckgz38QHs
quick sort algorithm
https://www.geeksforgeeks.org/quick-sort-algorithm/