Insertion Sort with ES6

March 25, 2019

Concept

打麻將或完撲克牌時我們很自然會用的排序法，假設從牌面的最左邊開始好了，第一輪就會從左邊數來第二張牌開始，姑且稱它為 unsortedCard，第二輪 unsortedCard 就是左邊數來第三張牌... 以此類推，有 n 項，便有共 n-1 輪

我們每一輪的任務便是，讓 unsortedCard 一一跟它左邊的牌比大小並交換位置，就像氣泡排序法一樣，直到正確的位置

Solution

//// 這是我一開始自己思考後的解法
const testArr=[34,23,566,342,1337,86,6,99]

const insertionSort = arr => {
  const cloneArr = [...arr];
  const cloneLength = cloneArr.length;
  // 第一張牌沒有可以比的對象，
  // 所以從第二張牌開始進行插入排序
  for (let i = 1; i < cloneLength; i++) {
    const unsortedCard = cloneArr[i];
    // 這一輪 "unSortedCard" 的位置，
    // 有機會往左移動
    let unsortedIndex = i;
    // j 是往前第幾張牌的 index
    for (let j = 1; j < i + 1; j++) {
      const sortedIndex = i - j;
      if (cloneArr[sortedIndex] > unsortedCard) {
        [cloneArr[unsortedIndex], cloneArr[sortedIndex]] = [cloneArr[sortedIndex], cloneArr[unsortedIndex]];
        // unsortedCard 與左邊一張牌交換後，
        // 位置 index 也要更新
        unsortedIndex--;
      } else {
        // 如果 unsortedCard 比 sortedCard 大的話，
        // 那就是位置正確了
        break;
      }
    }
  }
  return cloneArr;
};

//// 這是參考範例後的解法
// 主要差在，既然我的內迴圈有用 break，
// 代表迴圈次數並不固定，
// 那就可以使用 while 迴圈

const insertionSortWithWhile = arr => {
  const cloneArr = [...arr];
  const cloneLength = cloneArr.length;

  for (let i = 1; i < cloneLength; i++) {
    const unsortedCard = cloneArr[i];
    let unsortedIndex = i;

    while (cloneArr[unsortedIndex - 1] > unsortedCard) {
      [cloneArr[unsortedIndex - 1], cloneArr[unsortedIndex]] = [cloneArr[unsortedIndex], cloneArr[unsortedIndex - 1]];
      unsortedIndex--;
    }
  }

  return cloneArr;
};
console.log('--------');
console.log('unsorted arr', testArr);
console.log('insertionSort arr', insertionSort(testArr));
console.log(`insertionSortWithWhile arr`, insertionSortWithWhile(testArr));
console.log('--------');