삽입 정렬(Insertion Sort)은 흔히 카드를 정리하는 방식과 매우 유사한 정렬 기법입니다. 실제로 우리가 손에 든 카드를 오름차순으로 정렬할 때 사용하는 원리가 바로 삽입 정렬입니다. 이 기법에서는 데이터 집합에서 하나의 요소를 선택한 뒤, 그 요소가 들어갈 올바른 위치를 만들기 위해 앞쪽의 데이터 요소들을 한 칸씩 뒤로 밀어내고, 선택한 요소를 적절한 자리에 다시 삽입하는 방식으로 동작합니다.
삽입 정렬 기법의 복잡도
시간 복잡도: 최선의 경우 O(n), 평균 및 최악의 경우 O(n²)
공간 복잡도: O(1)
삽입 정렬은 이미 거의 정렬된 데이터를 처리할 때 매우 효율적이며, 추가적인 메모리 공간이 거의 필요하지 않아 제자리(in-place) 정렬 알고리즘으로 분류됩니다.
입력 − 정렬되지 않은 리스트: 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;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1]; // 한 칸씩 뒤로 이동
j--;
}
array[j] = key; // 올바른 위치에 삽입
}
}
int main() {
int n;
cout << "요소 개수 입력: ";
cin >> n;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "요소 입력:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "정렬 전 배열: ";
display(arr, n);
insertionSort(arr, n);
cout << "정렬 후 배열: ";
display(arr, n);
}
실행 결과
요소 개수 입력: 6
요소 입력:
9 45 23 71 80 55
정렬 전 배열: 9 45 23 71 80 55
정렬 후 배열: 9 23 45 55 71 80
위 실행 결과에서 볼 수 있듯이, 무작위로 나열된 숫자들이 삽입 정렬을 통해 오름차순으로 깔끔하게 정렬된 것을 확인할 수 있습니다.