[정렬] 삽입정렬

삽입정렬은

배열의 좌측을 정렬된 배열로 두면서

오른쪽의 엘리먼트를 점진적으로 배열의 좌측에 하나씩 삽입해가며 정렬해가는 방식이다.

 

• 버블정렬은 큰 값을 뒤로 빼면서 정렬해 나아가고
• 선택정렬은 작은 값을 앞에 두면서 정렬해 나아간다.
• 삽입정렬은 일단 좌측의 엘리멘트들을 정렬되었다고 본다.
  그리고 우측의 엘리먼트를 좌측의 엘리먼트와 하나하나 비교하며,
  우측 엘리먼트를 좌측 엘리먼트에 삽입해가면서 정렬한다.
  (이러한 이유로 좌측의 정렬된 엘리먼트가 점진적으로 증가한다.)

 

 

삽입정렬이다. 왼쪽부터 점차 정렬된다.

 

---

위의 설명에 따른 삽입 정렬의 의사코드는 아래와 같다.

 

의사코드

• 배열의 두번째 엘리먼트부터 시작한다. (첫번째 엘리먼트는 자체로 정렬이 되었다고 가정하기 때문)
• 이제 두번째 엘리먼트를 첫번째 엘리먼트와 비교하고, 필요하다면 값을 삽입한다.
• 비교를 마쳤다면 세번째 엘리먼트를 pick 한다. 그리고 왼쪽의 정렬된 엘리먼트와 하나씩 비교한다.
• 만약 세번째 엘리먼트가 두번째 엘리먼트보다 작고, 첫번째 엘리먼트보다 크다면 두 엘리먼트 사이가 세번째 엘리먼트의 위치가 된다.
• 배열의 정렬이 끝날때까지 반복한다.

 

아래는 의사코드에 따른 삽입정렬 알고리즘 코드이다.

 

---

삽입정렬

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {                         // (1)
        let currentVal = arr[i]                                    // (2)
        for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {  // (3)
            arr[j + 1] = arr[j]                                    // (4)
        }
        arr[j + 1] = currentVal                                    // (5)
    }
    return arr                                                     // (6)
}

/*
(1) 반복문의 시작은 1번째 인덱스로 한다. 0번째 인덱스는 이미 정렬이 되었다고 보기 때문이다.
(2) currentVal에 현재 arr[i]의 값을 저장한다. arr[i]의 실제적 엘리먼트 자체가 for문을 순회하며
    바뀌기 때문에 currentVal에 현재 arr[i]의 값을 저장하는 것이다.
(3) 내부 반복문의 조건이다. 조건이 맞지 않는다면 반복문이 깨지게 된다.
    먼저 j는 i보다 1 낮은 인덱스에서 시작하게 된다.
    j는 좌측의 정렬된 배열의 순회를 의미하므로 j가 0보다 작다면 반복문을 깨야한다.
    (배열의 인덱스가 -1이 되면 안되기 때문이다.)
    또한 arr[j]가 currentVal보다 크다면 반복문을 깨야 한다.
(4) 반복문이 유지된다면 arr[j]가 arr[currentVal]보다 크다는 의미이므로,
    arr[j + 1]의 값에 arr[j]를 할당해준다. 
    (큰 값을 하나씩 밀어준다고 생각하면 편하다.)
(5) 반복문이 깨진다면, arr[j + 1]에는 원래 있어야 할 값인 currnetVal 값을 할당 해준다.
    j + 1이 계속 나와 헷갈릴 수 있을텐데, 조건문에서 j는 계속 1씩 빠진 상태로 나온다.
(6) 반복문이 끝난다면 정렬된 배열을 리턴한다.

*/

 

사실 상당히 직관적이지 못하다.

 

이 이질감은 변수에 엮인 의미가 많아서 그렇다고 생각한다.

currentVal을 제외한 모든 변수들이 시시각각으로 변하기 때문이다.

(arr[i], arr[j + 1], arr[j] 는 알고리즘이 실행되면서 계속 변한다.)

 

따라서 그 변하는 값들을 잘 캐치해낸 뒤

컴퓨터가 작동하는 방식으로

하나하나 그려본다면

빠른 이해가 가능하다.

---

 

직관적인 이해를 돕기 위해 첫번째 싸이클의 로직을 그림판으로 그려보았다.

 

i는 1, j는 0, currentVal은 arr[i]으로 시작하며

배열은 [85, 70, 80, 75, 90, 100, 95] 로 주어진다.

 

 

변수에 값만 할당했고, 로직은 실행되지 않은 상태

일단 주어진 배열을 그대로 적고, 변수에 값을 할당시켜보자.

이 후 for문의 조건을 비교하면서 연산을 해나아간다.

 

---

 

반복문의 조건에 따라 arr[j + 1]이 arr[j]로 교체된다.

내부 반복문의 조건에 부합하므로, 

arr[j + 1]의 값을 arr[j]로 교체해준다.

 

---

 

반복문이 깨졌으므로 그 아래있는 로직이 실행된다.

내부 반복문이 깨졌으므로, 한 자리수 내려간 arr[j + 1] 에 currentVal이 할당된다.

 

 

---

 

이런식으로 하나하나 부수어가며 구현해보면

뚜렷하지는 않지만 로직이 약간 이해가 가기 시작한다.

 

위의 로직을 계속 타다보면

결국에는 정렬이 모두 이루어지게 된다.

 

정렬이 이루어졌다.

 

이해가 잘 가지 않으면

큰 종이를 하나 구해서 다 써보자.

써보는 방법밖에는 없다.

 

---

 

시간복잡도

삽입정렬은 왼쪽부터 값이 정렬되고,

정렬이 된 상태라면 반복문이 바로바로 종료되어 간편해 보일 수 있지만

어쨌든 큰 의미에서 for문에 for문을 사용하므로 시간복잡도는 O(N^2)이다.