[정렬 알고리즘] 삽입 정렬

삽입정렬은 우리가 카드를 정렬하듯 작동하는 간단한 정렬 알고리즘입니다.

 

8 7 1 2 9 6,   시작

7 8 1 2 9 6,   7은 8보다 앞에 오므로 그 앞에 삽입

1 7 8 2 9 6,   1은 8보다, 7보다 앞에 오므로 그 앞에 삽입

1 2 7 8 9 6,   2는 8보다, 7보다 앞에 오므로 그 앞에 삽입

1 2 7 8 9 6,   9는 8보다 크므로 그대로

1 2 7 6 8 9,   6은 9보다 8보다 작으므로 그 앞에 삽입

 

#include <bits/stdc++.h> 
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){
			arr[j+1] = arr[j];
			j--;			
		}
		//그 자리에 삽입한다. 
		arr[j+1]=key;
	}
} 

void printArray(int arr[], int n) 
{ 
	int i; 
	for (i = 0; i < n; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = { 12, 11, 13, 5, 6 }; 
	int n = sizeof(arr) / sizeof(int); 

	insertionSort(arr, n); 
	printArray(arr, n); 

	return 0; 
}

 

시간복잡도: O(n^2)

제자리정렬이며 안정정렬이다.

 

"정렬할 원소가 들어갈 자리를 찾아 삽입한다. 1번 인덱스 원소부터 마지막 인덱스 원소까지 실시한다."