삽입 정렬(Insertion Sort) - 자바스크립트, JS

1)for+while문

function insertionSort(arr){

    for(let i=0;i<=arr.length-1;i++){

      let numberToInsert = arr[i];

      let j = i - 1;

      while(j>=0 && arr[j] > numberToInsert){

        arr[j+1] = arr[j];

        j = j - 1;

      }

      arr[j+1] = numberToInsert

    }

  return arr;

}

const arr = [8, 20, -2, 4, -6];

console.log(insertionSort(arr)); //-6 -2 4 8 20

 

Big-O는 n^2

 

 

2)이중 for문

function insertionSort(arr) {

   for (let i = 0; i < arr.length; i++) {

      let j = 0;

      let tmp = arr[i];

      for (j = i - 1; j >= 0; j--) {

         if (arr[j] > tmp) arr[j + 1] = arr[j]

         else break;

      }

      arr[j + 1] = tmp;

   }

   return arr;

}

arr = [11, 7, 5, 6, 10, 9];

console.log(insertionSort(arr));

//Big O는 n2