一起用 JavaScript 來複習經典排序法吧！ - Huli's blog

[utterances-bot]

一起用 JavaScript 來複習經典排序法吧！ - Huli's blog

前言最近剛好上到 CS50 Week3，這一週的主題是：Algorithms，裡面介紹到了幾種經典的排序法，像是選擇排序、泡沫排序、插入排序以及合併排序。 我覺得身為一個軟體工程師，大概一輩子都脫離不了排序了，畢竟這是經典演算法之一嘛！與其每次要面試之前都凌亂

https://blog.huli.tw/2017/08/27/review-the-classical-sort-algorithm-with-javascript/

[unicornGL]

bubble sort 的部分貌似有誤， swapped = true; [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; 以上兩行順序應該要反過來， 不然會出現 TypeError: Cannot create property 'xxx' on boolean 'true'

[aszx87410]

@unicornGL 不好意思，有範例可以提供嗎？我試了一下看起來沒什麼問題（除了 function 應該改成 const 以外） 你貼的錯誤比較像是存取 swapped['xxx']，但看起來程式碼裡面應該沒有這個行為？或可能是我漏掉了

[unicornGL]

@aszx87410 抱歉，我指的是 optimzedBubbleSort 這個方法XD 錯誤訊息我下班再提供~~~

另外想問一下，Insertion Sort 在 while 裡面既然都已經移動 (`[arr[position], arr[position - 1]] = [arr[position - 1], arr[position]];``) 了，為什麼最後還要做插入的動作 (arr[position] = value;) 嗎？如果要用插入的方式，是不是只要做position--;` 就好？

[unicornGL]

我想了一下有點猜測，應該是想做類似 arr[position] = arr[position - 1] 之類的去移動數字？

[unicornGL]

可能類似這樣XD

const insertionSort = (arr) => {
  const length = arr.length

  // first number no need to move, so i start from 1
  for (let i = 1; i < length; i++) {
    const curr = arr[i]
    let p = i - 1

    // move numbers till find a place to insert current number
    while (p >= 0 && arr[p] > curr) {
      arr[p + 1] = arr[p]
      p--
    }

    // insert
    arr[p + 1] = curr
  }

  return arr
}