[Algorithm] C++ Insertion Sort (삽입정렬)

삽입정렬

• 앞의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법

 

삽입정렬 알고리즘

• i번째 원소를 1부터 k - 1번째 까지와 비교하여 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식

1. 각 패스에서 1부터 각 원소에 대해 하나씩 (n - 1) 비교한다.

2. 현재 원소는 이미 정렬된 하위 목록에 있는 원소와 비교하여 확인된다.

3. 이미 정렬된 하위 목록들을 살펴보면서 더 큰 원소를 오른쪽으로 이동한다.

예시

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheInsertionSort.html

아래 예시는 위의 예시의 다섯 번째 패스를 자세히 보여준다. 

알고리즘의 이 지점에서 17, 26, 54, 77, 93으로 구성된 5개 원소의 정렬된 하위 원소들이 존재한다. 

이때 이미 정렬된 항목에 31을 다시 삽입하려고 할 경우, 

93에 대한 첫 번째 비교시 다음 원소보다 크기에, 뒤쪽으로 이동하게 된다. 

이때 하위 원소인 77과 54도 31보다 크기에 이동된다. 

이때 비교 시 원소 26과 비교하면 변속 프로세스가 중지되고 원소 31이 아래 그림과 같이 열려있는 위치에 배치된다. 

이후에 정렬된 하위항목은 6개로 바뀝니다.

출처 - https://runestone.academy/ns/books/published/pythonds/SortSearch/TheInsertionSort.html

원소들 정렬 흐름은 아래 gif 파일로 확인할 수 있다.

 

 

삽입정렬 특징

• 배열이 길어질수록 효율이 떨어진다. 
• 구현이 간단하다는 장점이 있다.
• 선택 정렬이거나 거품 정렬과 같은 O(n^2) 알고리즘에 비교하면 빠르다.
• 안정 정렬이다.
• In-place 알고리즘이다.

 

시간복잡도

• 입력 자료의 구성에 따라 달라지며, 이미 어느정도 정렬되어 있는경우 가장빠르다.
• 비교 횟수

- 두개의 for루프의 실행 횟수

- 외부 루프 : (n - 1) 번

- 총 비교 횟수 : (n - 1)번

- 총 이동 횟수 : 2(n - 1)번

• 외부 루프 안의 각 반복마다 i번의 비교가 수행된다.
• 최악의 경우는 입력된 자료가 역으로 정렬된 경우이다. 아래에서 확인할 수 있다.

총 이동 횟수는 외부 루프의 각 단계마다 (i + 2)번 이동이 이루어지므로 다음과 같다.

따라서 최악의 경우 삽입정렬의 시간복잡도는 O(n^2)이다.

 

Code

C++

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 26, 54, 93, 17, 77, 31, 44, 55, 20 };
	int arrSize = 9;

	for (int i = 0; i < arrSize - 1; i++) 
	{
	
		for (int j = i + 1; j > 0 && arr[j - 1] > arr[j]; j--) {
			int temp = arr[j - 1];
			arr[j - 1] = arr[j];
			arr[j] = temp;
		}
		for (int a = 0; a < arrSize; a++)
			cout << arr[a] << ' ';
		cout << '\n';
	}

}