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

삽입 정렬은 배열을 그룹을 두 개로 나누어

E = {5,4,3,2,1} 이 있다고 하면

{5}를 key로 두고, 이보다 작은 index을 확인하여, 삽입하는 정렬 방법이다.

그 다음의 key는 4... 3.. 2 .. 1 순이다.

 

아래 소스에서는 j를 유심히 잘 봐야 한다.

#include<iostream>

using namespace std;

int main(){
	int size,i,j;
	cin >> size;
	
	int *arr = new int[size];
	
	for(i = 0; i < size; i++)
		cin >> arr[i];
	
	for(i = 0; i < size; i++){
		int key = arr[i];
		for(j = i-1; j >= 0; j--){
			if(key >= arr[j])
				break;
			arr[j+1] = arr[j];			
		}
		arr[j+1] = key;
	}
	
	for(i = 0; i < size; i++)
		cout << arr[i] << ' ';
	
	return 0;		
}

 

 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.