insertion Sort (javascript)

삽입정렬이란?

이런 것이라 한다. 개념설명은 잘 못하므로 패스!
저도 이 그림을 보고 이해했습니다.

문제

var insertionSort = function (array) {
  
    return array;
};

해석

이번 문제는 leetcode에서 나온 문제는 아니라서 저 그림을 토대로 풀어보겠습니다.
위에서 주어진 함수의 인풋으로 그림의 제일 첫번째줄인
let inputArray = [4, 3, 2, 10, 12, 1, 5, 6]
insertionSort(inputArray)라고 가정하고 진행하겠습니다.
한 단계씩 보면 inputArray[0] > inputArray[1] 비교하여 만약 충족한다면
서로의 위치를 바꾸는것을 볼수 있습니다.

제가 생각하기에 가장 중요한 부분은 for문이나 loop에서 index를 어떻게 해줄것인가
같습니다. 
그렇다면 풀이로 넘어 가겠습니다.

풀이1.

var insertionSort = function (array) {
 for (let i = 1; i < array.length; i++) {
   for (let j = 0; j < i; j++) { //i<j 가 포인트입니다.
     //i는 인덱스1부터 즉, 숫자3부터 시작하게되고, 
     //그렇게되면 j는 인덱스0부터, 즉 숫자 4부터 시작하게 됩니다.
     console.log("beforeChange", array);
     if (array[j] > array[i]) {
       let temporaryStorage = array[j]; //여기서 변수선언을 해주는 이유
       array[j] = array[i];             //array[j]=array[i]로 바뀌기 때문 
       array[i] = temporaryStorage;
       console.log("afterChange", array);
     }
   }
 }

 return array;
};

이해를 도우려 console.log를 찍어 두었고, 그에 관련한 로그 일부를 첨부하겠습니다.

저 이미지와 동일하게 동작하는 것을 볼수 있습니다.

후기

bubbleSort와 비슷한 느낌이 있었다.
그림을 보며 인덱스를 어떻게 할지 해결하고 나니
바로 풀린 문제이다.