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

개요

삽입정렬 알고리즘은 배열의 모든 인덱스를 확인하며 차례차례 자신의 적절한 위치를 찾아 정렬하는 알고리즘이다.

 

위의 자료에서 정렬된 부분은 분홍색, 정렬하고자 하는 키 값은 회색으로 표시했다.

여기서 키 값은 앞의 정렬된 분홍색 부분배열의 적절한 위치에 삽입된다.

이후, 키 값은 다음 인덱스로 넘어가고 이것을 반복해 배열 전체를 돌게되면 정렬이 되는 매커니즘이다.

---

코드

void Insertion_Sort(int arr[], int size){
	for(int j=1;j<size;j++){
		int key = arr[j];
		int i = j - 1;
		while(i > -1 && arr[i] > key){
			arr[i+1] = arr[i];
			i -= 1;
		}
		arr[i+1] = key;
	}
}

 

함수의 매개변수로는 배열과 배열의 크기를 받는다.

배열의 0번째 인덱스는 굳이 살펴볼 필요가 없기 때문에 1번째 인덱스부터 키 값으로 설정해,

while문을 통해 알맞은 위치에 자리를 내어주고, 마지막에 키 값을 알맞은 위치에 삽입한다.

살펴보고자 하는 인덱스인 i가 0보다 작아지면 안되므로 while문에 조건을 추가해주었다.

---

실행 결과

 

main 함수에 이것저것 추가해주고 코드를 돌려보면 다음과 같이 잘 작동하는 것을 볼 수 있다.

 

 

---

분석

• 삽입정렬 알고리즘의 시간 복잡도를 θ-표기법으로 나타내면 $ \theta (n^2) $ 이다.
• 삽입정렬 알고리즘은 크기가 작은 배열의 정렬에 효율적이다.