Sorting is one of the most fundamental of all algorithms in CS.
Even though many modern programming languages have built-in sorting functions, it's still a good thing to know how it work.
We're going to learn 6 different sorting algorithms in this course. It's good to know when to use which algorithms, as they excel in some certain cases.(在特定情況，時間複雜度高的演算法實際上是很好的演算法，不同的情況下，不能單純以時間複雜度來衡量演算法的好壞)

list of algorithms：1. bubble sort 2. insertion sort 3. selection sort

bubble sort

了解簡單的演算法，對後續的演算法會有較好的基礎

每 run 過一次 array 就將最小值推到最左邊。不斷地跟鄰居互換，互換到最前面去，就像泡沫一樣。

function bubbleSort(arr) {
  for (let i = 0; i <= arr.length-2; i++) {
    for (let j = arr.length-1; j >= i+1; j--) {
      if (arr[j] < arr[j-1]) {
        let temp = arr[j]
        arr[j] = arr[j-1]
        arr[j-1] = temp
      }
    }
  }
  return arr
}

優化

function bubbleSort(arr) {
  for (let i = 0; i <= arr.length-2; i++) {
    let swapping = false
    for (let j = arr.length-1; j >= i+1; j--) {
      if (arr[j] < arr[j-1]) {
        let temp = arr[j]
        arr[j] = arr[j-1]
        arr[j-1] = temp
        swapping = true
      }
    }
    if (swapping === false) {
      break
    }
  }
  return arr
}

overview of bubble sort

worst case performance：O(n^2)
best case performance：O(n) -> 本身由小到大排好，只要跑過一遍確定沒有任何的 swap，最後就會暫停這個 bubble sort
average case performance：O(n^2)，因為 nested forloop 所以絕大多數情況還是需要 O(n^2)

pf worst case performance

Insertion Sort

不斷做插入的動作

index = 0 是被排好的陣列，所以要檢查 index = 1，從他開始做 insert 的動作
設好目前的 key 值，也就是 index = j 的值
i = j-1 -> 對 j 前面所有 index 的值進行比較 (要將 key 與左邊的值進行比較，若比 key 大就要進行互換)
換到最後會多出 i + 1 這格，將 key 丟入

function insertionSort(arr) {
  for (let j = 1; j <= arr.length - 1 ; j++) {
    let key = arr[j]
    i = j - 1
    while ((i >= 0) && arr[i] > key) {
      arr[i+1] = arr[i]
      i--
    }
    arr[i+1] = key
  }
  return arr
}

overview of insertion sort

worst case performance：O(n^2)
best case performance：O(n) -> 本身由小到大排好，只要跑過一遍確定沒有任何的 swap，最後就會暫停這個 bubble sort
average case performance：O(n^2)，因為 nested forloop 所以絕大多數情況還是需要 O(n^2)

pf (1) and (2)

Selection Sort

對於未排列好的陣列找到他的最小值，然後將她與未排列好陣列裡面最左側值進行互換

function selectionSort(arr) {
  for (let i = 0; i < arr.length -1; i++) {
    let minIndex = i
    for (let j = i; j < arr.length ; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    // swap arr[minIndex] and arr[i]
    let temp = arr[minIndex]
    arr[minIndex] = arr[i]
    arr[i] = temp
  }
  return arr
}