삽입 정렬 (Insertion Sort)

1. 작동 방식

삽입 정렬은 정렬 알고리즘 중 하나로, 정렬되지 않은 부분 집합의 원소를 골라 정렬된 부분 집합의 알맞은 위치로 삽입하는 방식으로 작동한다.

출처 : https://www.geeksforgeeks.org/insertion-sort/

위의 그림처럼 정렬이 진행할 때 선택된 원소의 앞이 정렬된 부분 집합, 선택된 원소를 포함해 그 뒤가 정렬되지 않은 부분 집합으로 나뉜다. 정렬되지 않은 부분 집합의 맨 앞 원소가 정렬된 부분 집합으로 들어갈 자리를 비교를 통해 찾고 그 자리 뒤의 원소를 뒤로 옮긴 다음 해당 자리에 삽입한다.

2. 구현

// 구현부
void InsertionSort(int* arr, int n)
{
	int i, j, temp;
	
    // 첫 번째 원소는 정렬된 것으로 간주하고 두 번째 원소부터 진행
	for (i = 1; i < n; ++i)
	{
    	// 정렬될 원소를 따로 저장 (앞의 원소들이 밀리기 때문)
		temp = arr[i];
		
        // 알맞은 자리를 찾을 때까지 원소 하나씩 뒤로 밀기
		for (j = i; j > 0 && temp < arr[j - 1]; --j)
		{
			arr[j] = arr[j - 1];
		}
		
        // 찾은 자리에 별도로 저장한 원소 넣기
		arr[j] = temp;
	}
}

// 실행부
int main()
{
	int arr[]{ 2, 6, 5, 10, 8, 9, 3, 1, 7 };
    int size = sizeof(arr) / sizeof(arr[0]);
    
    InsertionSort(arr, size);
    for (const auto& ele : arr)
    {
    	std::cout << ele << " ";
    }
    
    // 출력 : 1 2 3 5 6 7 8 9 10
}

3. 시간 복잡도 / 공간 복잡도

- 시간 복잡도

최선 : $O(n)$

배열이 이미 정렬된 상태면 각 원소마다 앞의 원소와 비교를 한 번만 하면 되기 때문에 최선일 때의 시간 복잡도는 $O(n)$이다.

평균, 최악 : $O(n^2)$

앞의 원소와 비교하고 원소를 옮기는 횟수가 총 $1 + 2 + ... + (n - 1) = n(n - 1) / 2$ 이고, 배열이 역순인 최악의 상황일 때도 마찬가지이므로 시간 복잡도는 $O(n^2)$이다.

- 공간 복잡도

삽입 정렬은 추가적인 배열이나 메모리를 사용하지 않고 배열 내에서 원소의 이동이 이루어지기 때문에 공간 복잡도는 $O(1)$이다.

4. 장점 / 단점

- 장점

1. 원리가 단순하며 구현이 쉽다.
2. 안정적 정렬(stable sort)이므로 정렬된 데이터의 값이 같더라도 순서가 보장된다.
3. 제자리 정렬(In-place Sorting)이기 때문에 추가적인 메모리를 필요로 하지 않는다.

- 단점

1. 원소를 알맞은 자리에 삽입할 때 원소의 이동이 많이 발생한다.
2. 버블 정렬, 선택 정렬과 마찬가지로 주어진 데이터의 크기가 클 경우 다른 정렬 알고리즘에 비해 비효율적이다.