[알고리즘] 삽입 정렬(Insertion Sort)

다음과 같은 순서의 숫자 정렬들이 있을 때, 삽입 정렬의 정렬 방식은 다음과 같습니다.

숫자 배열: 8 3 2 4 9

 

8 3 2 4 9 -> 3 8 2 4 9 -> 3 2 8 4 9 -> 2 3 8 4 9 -> 2 3 4 8 9

 

삽입 정렬의 정렬 방식은 왼쪽 숫자와 오른쪽 숫자를 비교해서 크기가 역순이면 서로 바꾸게 됩니다.

위의 숫자로 설명하자면 처음 8과 3을 보게 됩니다. 8은 3보다 크기 때문에 8과 3의 위치를 바꾸게 됩니다. 

이렇게 되면 3과 8은 두 숫자만 보게되면 크기 순서로 이미 정렬이 완료된 상태입니다!

 

그 다음은 세번째 자리의 숫자인 2를 보게 됩니다. 그리고 2의 왼쪽 자리인 8을 봅니다. 8이 2보다 큼으로 8과 2의 자리를 바꿉니다. 그럼으로 3 2 8 4 9 가 됩니다.

 

그러고 나서 3과 2의 크기를 확인합니다. 3은 2보다 크기 때문에 서로 자리를 바꾸게 되면서 숫자 순서는 2 3 8 4 9가 됩니다. 

이렇게 되면 2, 3, 8은 크기 순서로 정렬이 완료가 됩니다.

 

그 다음에 4가 위와 같은 과정을 거쳐 2 3 4 8 9가 되고 9는 나머지 숫자들보다 크기가 더 크기 때문에 순서를 바꾸지 않습니다.

 

//  				 Selection Sort

#include<iostream>
#include<time.h>

int main(){
	clock_t start, end;
	double result;
	
	start = clock();
	int N;
	std::cout << "Plz enter the array numbers : ";
	std::cin >> N;
	
	int* arr = new int[N];
	std::cout << "Now enter all the elements of your array : ";
	for(int i = 0; i < N; i++){
		std::cin >> arr[i];
	}
	
	char show_process;
	while(1){
		std::cout << "Do u want to see the process?[y/n] : ";
		std::cin >> show_process;
		if(show_process == 'y' || show_process == 'n'){
			break;
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		}
		else
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		
	}
	
	int temp;
	for(int i = 1; i < N; i++){
		for(int j = i; j > 0 ; j--){
			if(arr[j] < arr[j-1]){
				temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;	
			}
		}
		if(show_process == 'y'){
			std::cout << i+1 << " round : ";
			for(int z = 0; z < N; z++){
				std::cout << arr[z] << " ";
			}
			std::cout << '\n';
		}
	}
	
	
	
	std::cout << "The final result is : ";
	for(int i = 0; i < N; i++){
		std::cout << arr[i] << " ";
	}
	std::cout << '\n';
	
	end = clock();
	result = (double)(end-start);
	std::cout << "Compile time : " << result << "ms"<< "\n";
	return 0;
}

삽입 정렬 또한 구현에 크게 어려운 부분은 없습니다. 

 

삽입 정렬의 시간 복잡도는 선택 정렬, 버블 정렬과 같이 O(N^2)이며 대부분의 상황에는 매우 비효율적입니다.

 

다만 이전 두 정렬법과는 달리 삽입 정렬은 특정한 상황에서 매우 효율적인 모습을 보입니다. 이 특정한 상황은 주어진 숫자들의 대부분이 정렬되었을 때의 상황입니다.

예를 들어서 2 3 4 5 1 같은 숫자 배열이 주어졌을 때 삽입 정렬을 사용하면 마지막 자리의 숫자인 1을 맨앞으로 옮기는 과정만 거치면 됩니다. 하지만 이전의 두 정렬은 숫자 배열 전체를 옮기는 과정을 진행하기 때문에 매우 비효율적이고 선택, 버블 정렬이외에도 이러한 상황에 삽입 정렬보다 더 효율적인 방법은 아직까지 없습니다.