Insertion Sort
특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬이라고 부른다.
특징
- 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. ( =특정한 데이터를 기준으로 왼쪽은 전부 정렬된 상태)
- 필요할 때에만 위치를 변경하므로 데이터가 거의 정렬되어 있을 때 효율적이다.
- 데이터를 하나씩 비교하므로 시간이 오래걸린다.
- -비교적 많은 원소들의 이동을 포함하며, 데이터의 수가 많고 크기가 클 경우 적합하지 않다.
시간 복잡도
👍최선의 경우 ( 이동 없이 1번의 비교만 이루어질 경우 )
- 비교횟수?
- 외부 루프 (N-1)번
O(N)
👎최악의 경우 (입력 자료가 역순일 경우)
- 비교 횟수?
- 외부 루프의 각 단계마다 (i+2)번의 이동 발생
O(N^2)
구현
- 오름차순을 기준으로 한다.
- 비교할 데이터의 왼쪽, 혹은 오른쪽에 삽입되는 두가지 경우만 판단한다.
- 여기서 왼쪽의 경우 비교할 데이터의 위치이고, 오른쪽의 경우는 (비교할 데이터 + 1)의 위치이다.
1. 첫번째 원소는 그 자체로 정렬되어 있다는 가정하에, 2번째 원소부터 비교를 시작한다.
2. 이미 정렬된 배열 부분과 비교(= 왼쪽으로 한칸씩 이동)하여 현재 데이터가 삽입될 위치를 찾는다.
3. 현재 데이터가 비교할 데이터보다 작다면 해당 위치에 삽입하면 된다.
적합한 위치에 삽입하는 과정을 (데이터의 갯수 - 1)번 반복하게 되면 모든 데이터가 정렬된다.
설명이 헷갈릴 수 있는데 직관적으로 정리하면,
1. 자신보다 낮은 인덱스의 원소들과 비교하면서
2.해당 데이터(비교할 원소의 데이터)보다 자신의 데이터가 더 작다면 비교할 원소를 오른쪽으로 옮기고,
3. 자신을 그 위치에 삽입하면 된다.
소스 코드
void InsertionSort()
{
int arr[10] = { 7,5,9,0,3,1,6,2,4,8 };
int arrSize = 10; // 배열의 총 사이즈
int minIndex = 0; // 가장 작은 값을 가지고 있는 인덱스
std::cout << "정렬 전 : ";
for (int i = 0; i < arrSize; ++i)
{
std::cout << arr[i] << " ";
}
std::cout << '\n';
// 삽입 정렬은 두번째 인덱스 부터 시작함 (첫번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문)
for (int currentIndex = 1; currentIndex < arrSize; ++currentIndex)
{
int currentValue = arr[currentIndex];
// 자신보다 작은 인덱스를 순회하며 현재 데이터의 자리를 찾는다.
for (int compareIndex = currentIndex-1 ; compareIndex >= 0; --compareIndex)
{
int compareValue = arr[compareIndex];
// currentValue가 비교할 값보다 더 작다면 위치를 옮긴다 데이터를 삽입한다.
if (currentValue < compareValue)
{
// 비교할 데이터는 오른쪽으로
arr[compareIndex + 1] = compareValue;
// 현재 데이터는 비교할 데이터가 원래 있었던 위치에 삽입
arr[compareIndex] = currentValue;
}
// currentValue가 더 크다면 해당 위치에서 멈춘다.
else
{
break;
}
}
}
std::cout << "정렬 후 : ";
for (int i = 0; i < arrSize; ++i)
{
std::cout << arr[i] << " ";
}
}
실행 결과
데이터가 거의 정렬이 되어있는 상황이라면 다른 정렬 알고리즘보다 삽입 정렬이 효율적일 수 있다.