자바스크립트로 삽입정렬 구현 (insertion sort in javascript)

삽입정렬이란?

삽입정렬이란 정렬된 부분과 정렬되지 않는 부분으로 나눠서 해당 요소가 정렬된 부분보다 값이 작다면 요소 교환을 실행하는 알고리즘입니다. 삽입정렬은 비교 알고리즘이므로 시간복잡도는 O(N2)입니다.. 초기 조건으로는 인덱스 0번째 값은 정렬이 되어 있다고 가정하고, 인덱스 첫 번째 요소부터 정렬하기 시작합니다.

예시

step 1

// initial array
[2,1,5,4,3]

첫 번째 요소부터 확인한다. (0번째 인덱스에 존재하는 데이터 2는 정렬되어 있다고 가정한다.) 1은 2보다 작으므로 swap한다.

// 현재 인덱스 1 
[1,2,5,4,3]

step 2

// 현재 인덱스 2
[1,2,5,4,3]

두 번째 요소를 확인한다. 데이터 5는 2보다 크므로 종료한다. (삽입정렬에서는 현재 요소의 왼쪽 값들은 모두 정렬되어 있다고 가정하므로, 현재 요소의 값(5)이 왼쪽 요소의 값(2)보다 크다면 정렬할 필요가 없으므로 종료한다

step 3

// 현재 인덱스 3
[1,2,5,4,3]

세 번째 요소를 확인한다. 데이터 4는 5보다 작으므로 swap한다.

// swap
[1,2,4,5,3]

데이터 4는 2보다 작으므로 종료한다.

step 4

// 현재 인덱스 4
[1,2,4,5,3]

네 번째 요소를 확인한다. 데이터 3은 5보다 작으므로 swap한다.

// 현재 인덱스 4
[1,2,4,3,5]

3은 4보다 작으므로 swap한다.

// 현재 인덱스 4
[1,2,3,4,5]

3은 2보다 크므로 종료한다.

마무리

[1,2,3,4,5]

이러한 과정으로 정렬을 진행하는 알고리즘이 삽입정렬입니다. 자바스크립트로 삽입정렬을 구현해보겠습니다.

자바스크립트로 삽입정렬 구현

function insertionSort(arr = []) {
// copy array
let result = [...arr];

for (let i = 1; i < result.length; i++) {
  let temp = result[i]; // 현재값 저장
  let aux = i - 1; // 정렬된 부분의 현재 인덱스

  // 좌측 값이 현재 값보다 클 때 swap
  while (aux >= 0 && result[aux] > temp) {
    result[aux + 1] = result[aux];
    aux--;
  }

  // 임시로 저장한 현재값을 정렬된 부분의 인덱스에 부여
  result[aux + 1] = temp;
}

return result;
}