삽입 정렬

July 28, 2023

삽입 정렬이란

배열의 요소 중에 두 번쨰 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

삽입 정렬하는 과정을 간단히 정리하면 다음과 같습니다.

두 번째 자료는 첫번째 자료와 비교
세 번째 자료는 두 번째와 첫 번째 자료와 비교
네 번째 자료는 세 번째, 두 번째와 첫 번째 자료와 비교
배열의 마지막요소 까지 위 과정을 반복합니다.

삽입 정렬 동작 과정

배열 [12, 11, 13, 5, 6]을 예를 들어 살펴 보겠습니다.

11은 12 보다 작으므로 두 개의 위치를 바꿉니다.
```
[12, 11, 13, 5, 6]
```
13이 12보다 크므로 두 개의 위치를 바꾸지 않습니다, 두 개의 위치가 바뀌지 않았다는 말은 13과 11을 굳이 비교하지 않아도 됩니다. 그 이유는 [11, 12]은 이미 그 전 과정에서 오름차순으로 정렬이 되었기 때문입니다.
```
[11, 12, 13, 5, 6]
```
5는 13보다 작으므로 두 개의 자리를 바꿉니다. 그리고 5는 12 보다 작으므로 두 개의 자리를 바꿉니다. 그리고 5는 11보다 작으므로 두 개의 자리를 바꿉니다.
```
[5, 11, 12, 13, 6]
```
6은 13 보다 작으므로 두 개의 자리를 바꿉니다. 그리고 6은 12보다 작으므로 자리를 바꿉니다, 그리고 6은 11보다 작으므로 자리를 바꿉니다. 마지막으로 6은 5보다 크므로 자리를 바꾸지 않습니다.
```
[5, 6, 11, 12, 13]
```

삽입 정렬 구현 코드

function insertSort(arr) {
  let temp;
  let j;

  for (let i = 1; i < arr.length; i++) {
    temp = arr[i];
    j = i - 1;

    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = temp;
  }
}

시간 복잡도 & 공간 복잡도

시간 복잡도

삽입 정렬의 최악의 경우 시간 복잡도는 O(N^2)입니다.
삽입 정렬의 평균적인 경우의 시간 복잡도는 O(N^2)입니다.
최선의 경우의 시간 복잡도는 O(N)입니다.

공간 복잡도

삽입 정렬의 공간 복잡도는 O(1)입니다.

삽입 정렬의 특징

이 알고리즘은 구현이 간단한 가장 간단한 알고리즘 중 하나입니다.
기본적으로 삽입 정렬은 작은 데이터 값에 효율적입니다.
삽입 정렬은 이미 부분적으로 정렬된 데이터 집합에 적합합니다.
삽입 정렬은 요소가 역순으로 정렬된 경우 정렬하는 데 최대 시간이 걸립니다. 그리고 요소가 이미 정렬된 경우 최소 시간(O(n))이 소요됩니다.
삽입 정렬을 제자리 정렬 알고리즘입니다.
삽입 정렬은 안정적인 정렬 알고리즘입니다.
삽입 정렬은 요소 수가 적을 때 사용됩니다. 입력 배열이 거의 정렬이 되어 있고 전체 큰 배열에 몇 개의 요소만 잘못 배치된 경우에도 유용할 수 있습니다.

참조

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

https://www.geeksforgeeks.org/insertion-sort/

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html