Sorting Algorithm

• Sorting
  1.We have covered :
  Selection sort : O(n^2)
  Insertion sort : O(n^2)
  Bubble sort : O(n^2)
  Heap sort : O(nlogn)
  2.Other efficient sorting algorithm
  Merge sort : worse case O(nlogn)
  Quick sort : average case : O(nlogn)

                      worse case : O\(n^2\)
  

• 術語
  1.in-place sorting
  在做sorting時，所需要的記憶體為固定的，不會與n成正比（所以O(1)）
  2.stable sorting
  一個向量內若出現兩個同樣的元素，前後順序不會因sorting而轉換
  3.external sorting
  若sorting資料量太大，因此需要放在外部儲存空間。而也因此，讀資料會非常慢，所以要考慮附近的資料（locality）

• C++ STL
  1.sort()
  2.stable_sort()
  有現成函數，不用再自己刻

• Quick sort vs. Heap sort