삽입정렬의 개념
삽입정렬은 말 그대로 새로운 데이터를 기존에 정렬된 데이터 사이에 삽입해 전체 데이터를 정렬하는 방식이에요. 어떤 데이터를 순차적으로 살펴보면서, 그 데이터를 알맞은 위치에 삽입하는 과정을 반복합니다.
쉽게 생각해보면, 우리가 카드를 정렬해서 손에 들고 있을 때와 비슷해요. 예를 들어 카드를 하나씩 뽑아 손에 들고 있는 카드 중에 적절한 위치를 찾아 넣는 것처럼요. 처음에는 한 장의 카드만 있으니 그 카드 자체가 정렬된 상태겠죠? 그 다음 카드부터는 이미 손에 든 카드들과 비교해서 알맞은 위치에 넣어주는 겁니다. 바로 이 과정이 삽입정렬이 하는 일과 똑같아요.
삽입정렬의 시간 복잡도
삽입정렬의 시간 복잡도는 데이터의 초기 상태에 따라 달라질 수 있어요. 만약 데이터가 이미 정렬된 상태라면 비교만 하고 삽입할 필요가 없기 때문에 매우 빠르게 처리됩니다. 이 경우, 최선의 시간 복잡도는 O(n)입니다. 즉, n개의 요소가 있을 때, n-1번만 비교하면 됩니다.
하지만 반대로, 데이터가 완전히 역순으로 정렬되어 있을 경우, 삽입할 때마다 모든 요소와 비교해야 하기 때문에 시간 복잡도가 급격히 늘어납니다. 이 경우 최악의 시간 복잡도는 O(n²)이에요.
삽입정렬의 예제
정렬되지지 않은 배열 `[5, 2, 4, 6, 1, 3]`이 있다고 가정해보죠.
1. 첫 번째 요소(5)는 이미 정렬된 상태라고 가정합니다.
2. 두 번째 요소(2)를 첫 번째 요소(5)와 비교합니다. 2가 더 작으므로 5의 앞에 삽입합니다. 배열은 `[2, 5, 4, 6, 1, 3]`이 됩니다.
3. 세 번째 요소(4)를 앞의 정렬된 요소들(2, 5)과 비교합니다. 4는 2보다는 크지만 5보다는 작으므로 5의 앞에 삽입합니다. 배열은 `[2, 4, 5, 6, 1, 3]`이 됩니다.
4. 네 번째 요소(6)를 삽입할 위치를 찾아 앞의 정렬된 요소들(2, 4, 5)과 비교합니다. 6은 5보다 크므로 그대로 세 번째 위치에 들어갑니다.
5. 다섯 번째 요소(1)를 앞의 정렬된 요소들(2, 4, 5, 6)과 비교하여 가장 앞에 삽입합니다. 배열은 `[1, 2, 4, 5, 6, 3]`이 됩니다.
6. 마지막 요소(3)를 앞의 정렬된 요소들(1, 2, 4, 5, 6)과 비교하여 2와 4 사이에 삽입합니다. 최종 배열은 `[1, 2, 3, 4, 5, 6]`이 됩니다.
삽입정렬의 특징
삽입정렬은 이해하기 쉽고 구현하기도 간단하지만, 소규모 또는 거의 정렬된 데이터에서는 매우 효율적입니다. 그러나 삽입정렬의 단점은 큰 데이터 집합에서는 비효율적이라는 거예요. 데이터가 많을수록 정렬 시간이 길어지죠. 이 때문에 대규모 데이터에서는 퀵 정렬이나 병합 정렬 같은 더 효율적인 알고리즘이 주로 사용됩니다.
