삽입 정렬 간단하고 직관적인 정렬 알고리즘으로, 데이터를 하나씩 정렬된 부분에 삽입하는 방식으로 작동합니다.
주로 소규모 데이터셋이나 거의 정렬된 데이터에 대해 효율적이라고 합니다.
- 정렬된 배열과 정렬되지 않은 배열로 나누어 생각합니다.
- 정렬되지 않은 배열에서 하나의 요소를 선택하여, 정렬된 배열의 적절한 위치에 삽입합니다.
- 이 과정을 반복하여 모든 요소가 정렬될 때까지 진행합니다.
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // 삽입할 요소
int j = i - 1;
// 정렬된 부분에서 key보다 큰 요소들을 한 칸씩 뒤로 이동
while (j >= 0 && arr[j] > key) {
// -- 해주어야되니 j + 1로 사용
arr[j + 1] = arr[j];
j--;
}
// key를 적절한 위치에 삽입
arr[j + 1] = key;
}
}
// 배열 출력 함수
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "정렬된 배열: ";
printArray(arr, n);
return 0;
}
- 두 번째 요소부터 시작하여(첫 번째 요소는 정렬된 상태로 간주), 해당 요소를 정렬된 부분에 삽입합니다.
- 삽입할 위치를 찾기 위해 정렬된 부분을 뒤로 이동하며 비교합니다.
- 적절한 위치를 찾으면 요소를 삽입합니다.
- 이 과정을 배열의 모든 요소에 대해 반복합니다.
버블 정렬과 선택 정렬과 달리
while반복문이 사용되었습니다.
코드 해석해보는 과정
여기서 봐야할건 첫 번째 요소는 정렬된상태로 간주하는겁니다.
배열 {12,11,13,5,6}에서 12는 정렬된것으로 간주하고
i = 1; j = 1(i) -1;
처음 arr[i] 인 11을 arr[j]인 12와 비교합니다.
와일문에서 j 가 0보다 커야되고 arr[j]가 arr[i](key)보다 클경우
이므로 현재 (12 , 11)으로 와일문 조건 해당
j--로
arr[1] = arr[0]
( arr[j + 1] = arr[j]) 로 바뀌고
(11 , 12 ...)
j--; // j == -1;
조건 풀리고
arr[j + 1] = key;
(arr [-1 + 1] = key(11))
현재 :
i = 2;
(11, 12 , 13, 5 , 6)
key = arr[i]; // 13
j = i - 1; // 1
반복문 조건( true && false) 안됨. // (12 > 13)
그대로 arr[j + 1] = key; // arr[2] = arr[2]; 그대로 유지
현재 :
i = 3;
(11, 12 , 13, 5 , 6)
key = arr[i]; // 5
j = i - 1; // 2 , arr[j] = 13
반복문 조건( true && true) // (13 > 5)
arr[3] = arr[2]; j--; //arr[j + 1] = arr[j]; // j-- // j == 1
arr[2] = arr[1]; j--; // j == 0
arr[1] = arr[0];j-- ; // j == -1
이런식으로 한칸씩 뒤로 밀어줍니다. 조건 문 나와서
그대로 arr[j + 1] = key; // arr[-1 + 1] = key; //5
5를 0번째 자리로 이동
마지막 인덱스는 위의 내용들을 이용해서 마무리
비교 후 적절한 위치에 삽입 하는 방식의 정렬인듯 합니다.
구현이 버블과 선택보다는 복잡하지만 아직은 간단하고 보기 편합니다.
데이터가 거의 정렬된 상태일 경우 성능이 좋습니다만
시간 복잡도가 O(n²)로, 큰 데이터셋에 대해서는 비효율적입니다.
최악의 경우에 대해서는 성능이 좋지 않습니다.
해본적 없는 방식이어서 그런지 신기합니다.