Algorithm JS - 삽입 정렬

jiny·2022년 9월 6일

JavaScript Algorithm

목록 보기

4/23

삽입 정렬

손 안의 카드를 정렬하는 방법과 유사(새로운 카드를 뽑으면 그 카드를 크기에 맞춰 정렬)
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
매 순서마다 해당 원소를 삽입 할 수 있는 위치를 찾아 해당 위치에 삽입
숫자 배열의 1번째 인덱스 부터 시작하여 마지막 요소까지 순회

순서

i는 1부터 시작

값이 i인 변수와 i-1인 변수 2개를 준비

배열[i]와 배열[i-1]를 비교하여 배열[i]가 더 크면 swap

i가 0이면 1세트 종료

숫자 배열 마지막 요소까지 순회

삽입 정렬 특징

장점

버블 정렬이나 선택 정렬에 비해 빠르며 안정적
이미 정렬되어 있는 경우나 자료의 수가 적은 정렬에 효율적 알고리즘

단점

비교적 많은 레코드들의 이동을 포함
배열의 수가 많고 자료의 크기가 클 경우 적합하지 않음

Big O

최악 시간 복잡도

O(n2)

최선 시간 복잡도

O(n)

평균 시간 복잡도

O(n2)

공간 복잡도

O(n)

소스코드

let answer = require("fs")
  .readFileSync(__dirname + "/input.txt")
  .toString()
  .trim()
  .split("\n")
  .slice(1)
  .join()
  .split(" ")
  .map((i) => Number(i));

for (let i = 1; i < answer.length; i++) {
  let idx = i - 1;
  let idx2 = i;
  while (true) {
    if (answer[idx] > answer[idx2]) {
      [answer[idx], answer[idx2]] = [answer[idx2], answer[idx]];
    }
    if (idx === 0) {
      break;
    } else {
      idx = idx - 1;
      idx2 = idx2 - 1;
    }
  }
}

console.log(answer);