Q1. Quick Sort是什麼

• 與前天介紹的 bubble sort 一樣，是一種計算排序的方法，但是此種演算法比起 bubble sort 平均所花費的時間更少

• 
  (表格來源 https://www.runoob.com/w3cnote/ten-sorting-algorithm.html )

• 時間複雜度，越小代表效率越好，關於詳細的時間複雜度，可以參考此篇文章：https://ithelp.ithome.com.tw/articles/10203082

• Quick Sort 擁有許多種變形，所以在網路上找相關文章時，有些文章 Quick Sort 方式有些微不同，但是他們整體概念基本上都是

1. 先從一串要排序的資料中，找出一個值，將他定為 Pivot
   
2. 然後比 pivot 小的放左邊，比 pivot 大的放右邊
   
3. 排序好一輪 pivot 的位置就會固定下來，重複第1與第2步驟，從剩下的數字選 pivot，將比較小的放左邊，比較大的放右邊
   

• 所以 Quick Sort 在實作上，有兩個要考慮的重點
  1. 在排序上，可能會有極端狀況導致效能不佳，所以 pivot 有很多選法：
     a. 每次選第一個元素
     b. 每次選最後一個元素
     c. 選擇特定位置（如中位數）的元素
     d. 隨機選擇任意元素
     • 假設有一個序列恰好「已/接近排序完成」，此時若選擇 第一個或是最後一個元素 作為 pivot，則會遇到極端情況，每次都要比較 N、N-1、N-2 .... 個數字
       • 
     • 若是能夠選擇中位數做為 pivot ，那麼就只要比較 N/2 與 N/2-1 的數量，類似二分搜的概念
       • 
  2. 如何將比較小的排左邊，比較大的排右邊，算法主要分為兩種：
     • Lomuto (較易實作與理解，常被做為教材，所以網路上教學文章主要都是使用此種方法)
       • 排序方法：
         • Lomuto 的 pivot 時常選定最後一個
         • 會有兩個指標指向開始
         • 
         • 指針分別：
           • j 指標專門停在比 pivot 大的位置
           • k 指標專門在 j 指標停之後(遇到比 pivot 大的值後)，停在比 pivot 小的位置
           • 當 k 與 j 指標都停止後，兩者的值就會做交換
           • 
           • 
         • 你會發現，比 pivot 大的數字，逐漸被往後放，最終 pivot 左邊都是比較小的，右邊都是比 pivot 大的值
         • Lomuto 影片連結：https://www.youtube.com/watch?v=86WSheyr8cM
       • Hoare (效率比 Lomuto 更好一些，交換次數更少)
         • 排序方法
           • Hoare 的 pivot 時常選定中位數
           • 會有兩個指標，一個指向開始，一個指向結尾
           • 
         • 指針分別：
           • k 指標逐漸往後，專門停在比 pivot 大的數字
           • j 指標逐漸往前，專門停在比 pivot 小的數字
           • 當 k 與 j 指標都停止後，兩者的值就會做交換 (把大的丟到右邊，把小的丟到左邊)
           • 
         • Hoare 影片連結：https://www.youtube.com/watch?v=NuQYFXmLUrM

Q2. 學會 Quick Sort 可以做什麼?

• 生活中時常會需要使用到排序好的資料 (尤其是可以處理資料量相對較多的)，例如
  • 全國基測分數從低到高排序
  • 世界財富排行榜

Lab. 明天要解的題目：912. Sort an Array

• 題目連結：https://leetcode.com/problems/sort-an-array/

• 我們上次使用 bubble sort 的算法解這一題，但是發現會效率不高，會出現 Time Limit Exceeded 的情況，我們這次使用今天介紹的 Quick Sort 的方法來解這一題

• 為了避免新加入的讀者需要往前翻題目，我們再將題目敘述一遍：

• 題目敘述：

  • 會有一個 nums 變數，裡面儲存著要排序的內容，我們要將內容由小到大進行排序
  • 

• 測資的 Input/Output：

  • 會拿到 nums 的變數，須回傳排序好的資料
  • 

• 題目的條件：

  • 可能會有 1~ 50000 個數字要進行排序
  • 每個數字會在 - 0.0005 ~ 50000 之間
  • 

• 看完題目你需要思考的是：

  • 使用 Quick sort 這個算法，會不會可能造成超時?
  • 有沒有其他排序方法可以使用 ?