삽입 정렬(Insertion Sort)

개념

정렬 대상의 앞의 데이터들과 비교하여 자리를 찾아가는 알고리즘입니다.

 

예제

다음과 같은 배열에 데이터가 저장되어 있을 때, 삽입 정렬을 통해 오름차순으로 정려해보겠습니다.

4

2

3

1

 

1회전

2를 앞에 데이터들과 비교합니다.

temp=2

삽입 정렬은 현재 데이터와 앞의 데이터들을 비교하기 때문에 2번째 데이터 값(인덱스 1)부터 시작한다.

 

2와 4를 비교합니다. 2가 4보다 작음으로 4를 뒤로 밀어내고 그 자리에 2가 들어갑니다. 

2

4

3

1

 

2회전

3을 앞에 데이터들과 비교합니다.

temp=3

 

3을 4와 비교합니다. 3이 4보다 작음으로 4를 밀어냅니다.

2

4

1

 

3을 2와 비교합니다. 3이 2보다 큼으로 비교를 멈추고 3이 빈 공간에 들어갑니다.

2

3

4

1

 

3회전

1을 앞에 데이터들과 비교합니다.

temp=1

1을 4와 비교합니다. 1이 4보다 작음으로 4를 밀어냅니다.

2

3

4

 

1을 3과 비교합니다. 1이 3보다 작음으로 3을 밀어냅니다.

2

3

4

 

1을 2와 비교합니다. 1이 2보다 작음으로 2를 밀어냅니다.

2

3

4

 

비교를 다 끝나고 빈 공간에 1이 들어갑니다.

1

2

3

4

 

코드구현 c++

int main()
{
	int arr[4] = { 4,2,3,1 };
	int i,j,temp;
	int n = 4;//배열의 크기

	for (i = 1; i < n; i++) {
		temp = arr[i];
		for (j = i-1; j >= 0; j--) {
			if (arr[j] > temp) arr[j + 1] = arr[j];//삽입 위치를 찾기위하여 데이터들을 밀어낸다.
			else break;//삽입 위치를 찾으면 break로 반복문을 빠져나간다
		}
		arr[j + 1] = temp;//데이터를 삽입한다.
	}
	for (i = 0; i < 4; i++) {
		std::cout << arr[i];
	}
}

 

비교횟수

삽입 정렬은 최선의 경우와 최악의 경우에 따라 횟수가 다릅니다.

최악의 경우 n*(n-1)/2번 비교를 진행합니다.

빅 오로 표기하면

O(n^2)

.