삽입 정렬은 카드 게임에서 손에 쥔 카드를 정렬할 때 사용하는 방식과 매우 유사한 정렬 기법입니다. 실제로 우리가 카드를 정렬할 때도 삽입 정렬의 원리를 자연스럽게 활용하고 있습니다. 이 기법은 데이터 집합에서 하나의 요소를 선택한 뒤, 해당 요소가 들어갈 적절한 자리를 만들기 위해 앞쪽 요소들을 한 칸씩 밀어내고, 선택한 요소를 올바른 위치에 다시 삽입하는 방식으로 동작합니다.
삽입 정렬의 동작 원리
삽입 정렬은 두 번째 요소부터 시작하여 각 요소를 이미 정렬된 앞부분과 비교하며 적절한 위치에 배치합니다. 구체적인 과정은 다음과 같습니다.
- 현재 인덱스
i의 값을 키(key)로 저장합니다. - 키 값보다 큰 요소들을 뒤로 한 칸씩 이동시킵니다.
- 키 값이 들어갈 올바른 위치를 찾으면 그곳에 키를 삽입합니다.
- 배열의 끝까지 위 과정을 반복합니다.
삽입 정렬 기법의 복잡도
- 시간 복잡도: 최선의 경우 O(n), 평균 및 최악의 경우 O(n²)
- 공간 복잡도: O(1) — 추가 메모리 없이 제자리(in-place) 정렬이 가능합니다.
데이터가 거의 정렬되어 있는 상태라면 내부 반복문이 빠르게 종료되므로 O(n)에 가까운 성능을 보이며, 이러한 경우 삽입 정렬은 매우 효율적입니다.
입력과 출력
입력: 정렬되지 않은 리스트: 9 45 23 71 80 55 출력: 정렬 전 배열: 9 45 23 71 80 55 정렬 후 배열: 9 23 45 55 71 80
알고리즘
insertionSort(array, size)
입력 − 데이터 배열과 배열의 총 요소 개수
출력 − 정렬된 배열
Begin
for i := 1 to size-1 do
key := array[i]
j := i
while j > 0 AND array[j-1] > key do
array[j] := array[j-1];
j := j – 1
done
array[j] := key
done
End
C++ 구현 예제
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i]; // 현재 값을 가져옴
j = i;
// key보다 큰 요소들을 한 칸씩 뒤로 이동
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key; // 올바른 위치에 삽입
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
}
실행 결과
Enter the number of elements: 6 Enter elements: 9 45 23 71 80 55 Array before Sorting: 9 45 23 71 80 55 Array after Sorting: 9 23 45 55 71 80
마무리
삽입 정렬은 구현이 간단하고 작은 규모의 데이터나 거의 정렬된 데이터에 강점을 가진 직관적인 정렬 알고리즘입니다. 평균적으로 O(n²)의 시간 복잡도를 가지기 때문에 대량의 데이터에는 부적합하지만, 안정적인(stable) 정렬 방식이며 제자리 정렬이 가능해 메모리 효율성이 좋다는 장점이 있습니다.