삽입 정렬과 선택 정렬은 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이 증가합에 따른 두 정렬의 실행 시간 증가 추이
'자료구조' 카테고리의 다른 글
[자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙 (0) | 2021.06.03 |
---|---|
[자료구조] 이중 연결 리스트 (Double Linked List) C/C++ 구현 - 알고리즘 (0) | 2020.10.30 |
[자료구조] 연결 리스트 (Linked List) C/C++ 구현 - 알고리즘 (0) | 2020.10.30 |
[자료구조] 큐 (Queue) C/C++ 구현 - 알고리즘 (0) | 2020.10.30 |
[자료구조] 스택 (Stack) C/C++ 구현 - 알고리즘 (0) | 2020.10.30 |