정렬된 상태를 파고드는 기술
크리스는 서버에서 받아온 '로그 데이터'를 시간순으로 정렬하는 작업을 하고 있다.
그런데 이 데이터는 특이하다. 이미 99%는 시간순으로 정렬되어 있고, 아주 가끔 늦게 도착한 로그 몇 개만 순서가 뒤섞여 있다.
"이미 거의 다 정렬되어 있는데, 버블 정렬이나 선택 정렬을 쓰면 처음부터 끝까지 다시 비교하느라 시간 낭비잖아?"
"중간에 낀 녀석만 쏙 뽑아서 제 자리에 끼워 넣으면(Insert) 끝나는 거 아닐까?"
그렇다. 우리가 카드 게임을 할 때 카드를 정리하는 방식, 그리고 데이터가 거의 정렬되어 있을 때 빛을 발하는 알고리즘. 바로 삽입 정렬(Insertion Sort)이다.
1. 카드 게임의 지혜
삽입 정렬의 로직은 아주 직관적이다.
우리가 손에 쥔 카드를 왼쪽부터 순서대로 정리한다고 상상해 보자.
핵심은 "앞부분은 이미 정렬되어 있다고 가정하고, 새로운 카드를 적절한 위치에 삽입한다"는 것이다.
2. 자바스크립트로 구현하기
구현의 핵심은 "뒤에서 앞으로(Backwards)" 비교한다는 점이다. 나보다 큰 녀석들은 한 칸씩 뒤로 밀어내고(Shift), 내가 들어갈 빈자리가 생기면 그곳에 안착한다.
function insertionSort(arr) {
// 1. 두 번째 요소(i=1)부터 시작한다. (첫 번째는 이미 정렬됐다고 침)
for (let i = 1; i < arr.length; i++) {
let currentVal = arr[i]; // 현재 정리할 카드
let j;
// 2. 내 앞(j)의 카드들과 비교하며 뒤로 거슬러 올라간다.
// 조건: j가 0보다 크거나 같고, 앞의 카드가 나(currentVal)보다 크면?
for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
arr[j + 1] = arr[j]; // 앞의 카드를 한 칸 뒤로 밀어낸다. (Copy)
}
// 3. 반복문이 끝난 곳(나보다 작은 카드를 만난 곳) 바로 뒤에 앉는다.
arr[j + 1] = currentVal;
console.log(`Step {i}:`, arr); // 과정을 확인해보자
}
return arr;
}
insertionSort([2, 1, 9, 76, 4]);3. 왜 '삽입 정렬'이 특별한가?
코드만 보면 이중 반복문이라 버블, 선택 정렬과 비슷해 보인다. 하지만 결정적인 차이가 있다.
스마트한 중단 (Smart Break)
버블 정렬과 선택 정렬은 조건에 상관없이 무조건 끝까지 비교한다.
하지만 삽입 정렬은 내부 루프(j)를 돌다가 나보다 작은 값을 만나면 그 즉시 멈춘다. 내 앞은 이미 정렬되어 있으니 더 볼 필요가 없기 때문이다.
최고의 시나리오: O(N)
만약 데이터가 이미 정렬되어 있다면?
삽입 정렬은 각 요소를 한 번씩만 확인하고 "어? 내 앞이 나보다 작네? 그럼 난 여기 있으면 되겠다"하고 바로 넘어간다.
이때의 시간 복잡도는 O(N)이다. 버블, 선택 정렬(O(N^2))과는 비교도 안 되게 빠르다.
실시간 데이터 처리 (Online Algorithm)
데이터가 한 번에 주어지는 게 아니라, 실시간으로 하나씩 들어오는 상황(라이브 스트리밍 채팅 등)에서도 유용하다. 데이터가 들어올 때마다 제자리를 찾아 꽂아주면 되기 때문이다.
4. 단점은 없을까?
물론 만능은 아니다.
데이터가 역순(Reverse)으로 정렬되어 있다면 최악이다.
[5, 4, 3, 2, 1]을 정렬하려면 모든 요소를 매번 맨 앞까지 이동시켜야 하므로 O(N^2)의 시간이 걸린다. 데이터가 무작위로 섞여 있을 때도 평균적으로 O(N^2)이다.
핵심 정리
지금까지 배운 세 가지 정렬(버블, 선택, 삽입)은 구현이 쉽지만, 데이터가 10만 개만 넘어가도 느려서 못 쓴다.
이제부터는 차원이 다른 속도를 보여주는 O(N log N)의 세계로 진입한다.
"데이터를 쪼개면 빨라진다"는 분할 정복(Divide and Conquer)의 마법.
그 첫 번째 주자, 합병 정렬(Merge Sort)을 만나보자.