[자료구조] 삽입 정렬 (InsertionSort), 선택 정렬 (Selection Sort) C/C++ 구현 및 비교 실험

삽입 정렬과 선택 정렬은 O(N^2)의 비효율적인 정렬 방법입니다. 

효율적인 정렬을 구현하고 싶으시면 아래 링크를 봐주세요

2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이

머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이

---

삽입 정렬의 코드는 아래와 같습니다. 

두 번째 원소 ( i = 2)부터 시작하여 바로 앞 ( 0 ~ i-1 )의 정렬된 원소들과 비교하여 삽입 위치를 지정하고 삽입된 위치부터 오른쪽으로 한 칸씩 시프트 하는 방법으로 동작합니다.

삽입 정렬 원리

void insertion_sort(int* arr, int n) {
	for (int i = 1; i < n; i++) {
		int current_number = arr[i]; // 삽입해야할 수
		int _index = i - 1; // current_number가 들어갈 인덱스 
		for (;_index > -1; _index--) {
			if (arr[_index] > current_number) { // 정렬된 구간내 j번째 수가 current_number 보다 크다면
				arr[_index + 1] = arr[_index]; // 뒤로 한칸 이동
			}
			else { // 정렬된 구간 내 j번째 수가 current_number 보다 작다면
				break; // 삽입 위치를 찾았으므로 반복문 탈출
			}
		}
		// 해당 위치에 current_number 삽입
		arr[_index+1] = current_number;
	}
}

 

삽입 정렬은 정렬된 데이터에 대하여 O(N)으로 빠르게 동작하며 이외의 경우에서는 O(N^2)의 복잡도를 갖습니다.

---

선택 정렬의 코드는 아래와 같습니다.

선택 정렬은 정렬이 안된 구간 (0~ i)에서 가장 큰 수를 찾아 정렬 된 바로 앞의 ( i ) 원소와 교체하는 방법입니다.

(반대로 구현하면 최소값을 찾아 앞에서부터 교체하면 됩니다)

void selection_sort(int* arr, int n) { // 입력 배열, 배열 크기 
	int last = n - 1; // 찾은 가장 큰 값이 들어가야하는 배열 인덱스  
	for (int i = 0; i < n; i++) { // n번 반복
		int _max = 0; // 찾은 가장 큰 값, 양의 정수만 입력되므로 초기 값을 0으로 설정
		int _index = -1; // 큰 값이 위치한 인덱스 번호 
		for (int j = 0; j <= last; j++) { 
			if (_max < arr[j]) { // 현재 탐색하는 값이 더 크다면
				_max = arr[j]; // 가장 큰 값 초기화
				_index = j; // 큰 값이 위치한 인덱스 저장
			}
		}
		// _max는 정렬이 안된 0 ~ last 사이에 가장 큰 값이며 배열 내 해당 값의 위치는 _index 이다
		// 두 수 교환
		int temp = arr[last];
		arr[last] = arr[_index];
		arr[_index] = temp;

		// last부터 배열 끝까지 정렬된 상태이므로 한칸 앞으로
		last = last - 1; 
	}
}

 

 

---

 

A. 정렬이 안된 데이터가 주어지는 경우

동일한 n으로 여러 번 실험하여, 어느 정렬이 더 빠른지 비교해보자, 50번 수행한 결과 평균 측정값

n	선택 정렬 (ms)	삽입 정렬 (ms)
100	0.033970	0.012240
1000	4.345330	0.882980
10000	418.746140	93.581450

n이 증가합에 따른 두 정렬의 실행 시간 증가 추이

삽입 정렬의 안정성이 더 뛰어난 결과를 확인 가능합니다.

 

B. 정렬된 데이터가 주어지는 경우

동일한 n으로 여러 번 실험하여, 어느 정렬이 더 빠른지 비교해보자, 50번 수행한 결과 평균 측정값 

n	선택 정렬 (ms)	삽입 정렬 (ms)
100	0.041520	0.001090
1000	3.963410	0.009800
10000	404.268900	0.100700

 

n이 증가함에 따른 두 정렬의 실행 시간 증가 추이

정렬된 입력에 대하여 삽입 정렬이 더 빠르게 동작합니다.

 

B. 역순으로 정렬된 데이터가 주어지는 경우

동일한 n으로 여러 번 실험하여, 어느 정렬이 더 빠른지 비교해보자, 50번 수행한 결과 평균 측정값

n	선택 정렬 (ms)	삽입 정렬 (ms)
100	0.043890	0.019350
1000	3.559050	1.773330
10000	381.963280	197.239680

 

n이 증가합에 따른 두 정렬의 실행 시간 증가 추이