[정렬] 삽입정렬
삽입정렬은
배열의 좌측을 정렬된 배열로 두면서
오른쪽의 엘리먼트를 점진적으로 배열의 좌측에 하나씩 삽입해가며 정렬해가는 방식이다.
- 버블정렬은 큰 값을 뒤로 빼면서 정렬해 나아가고
- 선택정렬은 작은 값을 앞에 두면서 정렬해 나아간다.
- 삽입정렬은 일단 좌측의 엘리멘트들을 정렬되었다고 본다.
그리고 우측의 엘리먼트를 좌측의 엘리먼트와 하나하나 비교하며,
우측 엘리먼트를 좌측 엘리먼트에 삽입해가면서 정렬한다.
(이러한 이유로 좌측의 정렬된 엘리먼트가 점진적으로 증가한다.)
위의 설명에 따른 삽입 정렬의 의사코드는 아래와 같다.
의사코드
- 배열의 두번째 엘리먼트부터 시작한다. (첫번째 엘리먼트는 자체로 정렬이 되었다고 가정하기 때문)
- 이제 두번째 엘리먼트를 첫번째 엘리먼트와 비교하고, 필요하다면 값을 삽입한다.
- 비교를 마쳤다면 세번째 엘리먼트를 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] 에 currentVal이 할당된다.
이런식으로 하나하나 부수어가며 구현해보면
뚜렷하지는 않지만 로직이 약간 이해가 가기 시작한다.
위의 로직을 계속 타다보면
결국에는 정렬이 모두 이루어지게 된다.
이해가 잘 가지 않으면
큰 종이를 하나 구해서 다 써보자.
써보는 방법밖에는 없다.
시간복잡도
삽입정렬은 왼쪽부터 값이 정렬되고,
정렬이 된 상태라면 반복문이 바로바로 종료되어 간편해 보일 수 있지만
어쨌든 큰 의미에서 for문에 for문을 사용하므로 시간복잡도는 O(N^2)이다.