삽입 정렬 - 여기 말고 저기 빈 자리 가서 앉으세요

이번 포스팅 내용은 삽입정렬입니다.
삽입 정렬은 선택 정렬의 정렬방식과 유사합니다.
선택 정렬이 정해진 위치에 조건에 부합하는 자료구조 내 원소들끼리 비교하여 하나의 원소를 배치 했다면
삽입 정렬은 조건에 부합하는 자료구조 내 원소들이 정해진 위치를 향해 이동합니다.
그럼 아래에서 더 자세히 알아보겠습니다.

---

1. 삽입 정렬 ( Insertion Sort )이란?

삽입정렬은 이름에서 대략적인 동작 방식을 표현하고 있습니다.
정렬하고자 하는 공간을 임시로 빈 공간으로 만들고 비교 대상 데이터들이 조건에 부합한다면 해당 위치로 이동시킵니다.

기존에 해당 위치에 있던 데이터는 남아있는 빈 공간으로 "삽입" 됩니다.

 

---

 

2. 삽입 정렬의 진행

더 자세히 알아 볼까요?
삽입정렬은 자료구조 내 두번째 원소부터 마지막 원소까지 순차적으로 이동하며 시행됩니다.
각 패스스루 마다 채워 넣을 위치가 주어지고 해당 위치에 있는 데이터를 임시 공간에 저장하여 해당 위치를 빈 공간으로 만들어 줍니다.
이 후 임시 공간에 있는 데이터와 빈공간 보다 앞에 있는 ( 왼쪽에 위치한 ) 데이터들을 비교하며 조건에 부합할 시 빈공간을 향해 (오른쪽으로) 이동하여 빈 공간을 매꿉니다.
조건에 부합하지 않는 원소를 만나거나 순회 범위의 시작부분에 도달하게 되면 해당 패스스루를 종료합니다.

 

---

 

3. 삽입 정렬의 코드 구현

function insertionSort(arr) {
    // index : 패스스루가 채워 넣을 위치
    for (let index = 1; index < arr.length; index++) {
        // position : 비어있는 자료구조 위치
        let position = index;
        // temp : 패스스루가 채워넣을 위치의 데이터
        const temp = arr[index];
        // 빈 공간이 시작 위치까지 이동 할 때까지 진행
        while (position > 0) {
            // 저장해놓은 데이터와 비어있는 공간의 앞(왼쪽)에 위치한 데이터를 비교하여
            // 비어있는 공간의 앞(왼쪽)에 위치한 데이터 크다면 비어있는 공간의 앞의 데이터 뒤로(오른쪽) 이동
            // 이동하면 이동한 데이터의 위치는 비어있는 상태
            if (temp < arr[position - 1]) {
                arr[position] = arr[position - 1];
                position--;
            } else {
                // 조건에 부합하지 않는 값 직면 시 패스스루 종료
                break;
            }
        }
        // 비어있는 공간에 패스스루가 채워넣을 위치에 존재하던 데이터 삽입
        arr[position] = temp;
    }
    return arr;
}

 

---

4. 삽입 정렬의 효율성

• 시간 복잡도

* 최악의 시나리오인 내림차순인 경우 범위에 있는 모든 데이터를 이동해야 하기 때문에
  1번째 패스스루에서 $N-1$단계
  2번째 패스스루에서 $N-2$단계
  ....
  마지막 패스스루에서 1단계로

  $(N-1) + (N-2) +... + 1 = N(N-1)/2$

  $O(N(N-1)/2)$ = $O(N^2)$ 가 나오게 됩니다.

* 최선의 시나리오인 오름차순 정렬이 되어있는 경우 각 패스스루마다 비교 연산이 1회만 이루어지기 때문에
  $O(N)$ 가 나오게 됩니다.

• 공간 복잡도

주어진 공간 내에서 교환을 통해 정렬되므로 $O(N)$입니다.

 

---

 

4. 삽입 정렬의 장단점

• 장점

* 거품 정렬, 선택 정렬 등 동일한 $O(N^2)$ 시간복잡도 카테고리의 정렬 알고리즘 중 상대적 효율성 높음
* 자료 구조 내에서만 교환이 이루어져 별도 메모리 사용 없음 => 제자리 정렬
* 중복된 값인 경우에도 입력 순서로 정렬 보장 => 안정 정렬 

• 단점

* 평균과 최악의 시나리오의 시간 복잡도가 비효율적 - $O(N^2)$

---

마치며

다른 분들은 단순한 정렬 알고리즘이라 하시는데 저에게는 단순하지 않네요....
참고 자료에서 손안에 있는 카드를 정렬하는 방식과 비슷하다는 글을 보았는데  참 와닿았습니다.

 

출처

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