[JS] 삽입정렬

[Javascript] 삽입정렬

프론트엔드 공부를 하면서 javascript에 익숙해져야 한다는 생각이 들면서 javascript로 알고리즘 공부를 병행하기로 했다.

알고리즘으로 꾸준하게 코드를 작성하다 보면 js에 빨리 익숙해 질 수 있을 것같다!

삽입정렬

(출처: 위키피디아_삽입정렬)

삽입정렬은 배열에서 0번은 두고 1번부터 앞에 요소들과 비교해서 자신의 위치를 설정해 놓는 것이다.

예시로 [1,3,2,5]로 설명하겠다.

1. 3과 1을 비교 -> 3이더 크기 때문에 냅둔다. --[1,3,2,5]
2. 2와 앞에 1,3 을비교 1<2<3 이므로 1,3 사이에 들어간다. --[1,2,3,5]
3. 5와 앞에 1,2,3을 비교 --[1,2,3,5]

삽입정렬은 2중 반복문을 사용하기 때문에 시간 복잡도는 O(N^2)으로 오랜 시간이 걸리는 축에 속한다.

삽입정렬 코드

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let currentNum = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > currentNum) {
      //앞에 있는 값이 더 크다면 한칸 오른쪽에 넣어준뒤, currentNum을 j자리에 넣고 반복
      arr[j + 1] = arr[j];
      arr[j] = currentNum;
      currentNum = arr[j];
      j--;
    }
  }
  return arr;
};