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

문제

다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.
 1 5 8 10 7 6 3 2 9 4

 

알고리즘 종류

• Selection sort (내부 : 교환)
• Bubble Sort (내부 : 교환)
• Insertion Sort (내부 : 삽입)
• Quick Sort (내부 : 교환)
• Shell Sort (내부 : 삽입)
• Merge Sort (내부 : 병합)
• Heap Sort (내부 : 선택)
• Radix Sort (내부 : 분배)

 

삽입 정렬 알고리즘이란?

삽입 정렬은 두 번째 원소부터 시작해서, 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후

앞의 원소를 뒤로 옮기고 지정한 자리에 원소를 삽입하여 정렬하는 알고리즘이다.

 

 

정렬된 부분은 왼쪽, 정렬할 부분을 오른쪽으로 구별을 한다.

ex) 10, 7, 6, 3, 2

 

파란색 : 이미 정렬된 부분

흰색 : 정렬해야 하는 부분

10

7

6

3

2

7

10

6

3

2

6

7

10

3

2

3

6

7

10

2

2

3

6

7

10

 

 

 

 

삽입 정렬 알고리즘

#include <string>
#include <vector>
#include <iostream>
using namespace std;

void main() {
	vector<int> target = { 1, 5, 8, 10, 7, 6, 3, 2, 9, 4 };
	int n = target.size();
	int temp;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j > 0; j--) {
			if (target[j] < target[j - 1]) {
				temp = target[j - 1];
				target[j - 1] = target[j];
				target[j] = temp;
			}
			else
				break;
		}

		// i번째 정렬 결과 출력
		for (int c = 0; c < n; c++) {
			cout << target[c] << " ";
		}
		cout << endl;
	}
}

 

  위의 소스코드는 서로인접한 값 array[j] 와 array [j+1] 를 비교해서 더 작은값을 앞으로 보내는 과정을 가집니다.

 

삽입 정렬(bubble sort) 알고리즘의 특징

장점

- 구현이 간단하다

- O(n^2)인 선택 정렬이나 버블 정렬과 같은 알고리즘에 비해 안정적이고 빠른 정렬이다.

 

단점

- 배열이 길어지면 효율이 점차 떨어진다.

 

삽입 정렬의 시간복잡도

최고 O(N)

이동없이 1번씩 비교할 경우

 

최저 O(N^2)

n-1, n-2, n-3, ... , 2, 1 번 = n(n-1)/2

T(n) = O(n^2)

 

정렬 알고리즘	최고	평균	최저	Run-time
삽입 정렬	n	n^2	n^2	7.438
선택 정렬	n^2	n^2	n^2	10.842
버블 정렬	n^2	n^2	n^2	22.894
셸 정렬	n	n^1.5	n^2	0.056
퀵 정렬	nlog2n	nlog2n	n^2	0.014
힙 정렬	nlog2n	nlog2n	nlog2n	0.034
병합정렬	nlog2n	nlog2n	nlog2n	0.026