Selection Sort (선택 정렬)
#include <cstdio> #include <cstdlib> using namespace std; void selection_sort(int *nums, int N) { int min, min_idx; for(int i=0; i<N-1; i++) { min_idx = i; min = nums[i]; for(int j=i+1; j<N; j++) { if(min > nums[j]) { min = nums[j]; min_idx = j; } } nums[min_idx] = nums[i]; nums[i] = min; } } int main(void) { int N, *nums; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) scanf("%d", &nums[i]); selection_sort(nums, N); for(int i=0; i<N; i++) printf("%d ", nums[i]); printf("\n"); free(nums); return 0; } | cs |
[내용]
N개의 숫자를 정렬할 때, index를 0~N-2 에서부터 N-1 까지 보면서, 가장 작은 수를 선택해서 맨 앞과 바꿔주면서 정렬해 나가는 방식이다.
맨 처음부터 마지막 중 가장 작은 수를 찾아서 첫 번째와 바꿔주고,
두 번째부터 마지막 중 가장 작은 수를 찾아서 두 번째와 바꿔주는 식으로 진행한다.
[특징]
- 비교 연산이 많이 사용된다.
- 값을 실제로 교환하는 횟수는 상대적으로 적다.
Bubble Sort (버블 정렬)
[예시 코드]
#include <cstdio> #include <cstdlib> using namespace std; void bubble_sort(int *nums, int N) { int temp; for(int i=0; i<N-1; i++) { for(int j=1; j<N-i; j++) { if(nums[j-1] > nums[j]) { temp = nums[j-1]; nums[j-1] = nums[j]; nums[j] = temp; } } } } int main(void) { int N, *nums; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) { scanf("%d", &nums[i]); } bubble_sort(nums, N); for(int i=0; i<N; i++) printf("%d ", nums[i]); printf("\n"); free(nums); return 0; } | cs |
[내용]
앞쪽부터 뒷쪽까지 2개의 숫자씩을 비교해가며, 오른쪽이 더 작은 경우 값을 교환해준다.
이를 N번 진행하면 전체 숫자의 정렬이 완료된다.
[특징]
- 비교와 값의 교환이 많이 발생한다.
Insertion Sort (삽입 정렬)
#include <cstdio> #include <cstdlib> using namespace std; void insertion_sort(int *nums, int N) { int t, idx; for(int i=1; i<N; i++) { t = nums[i]; idx = i; while(nums[idx-1] > t && idx > 0) { nums[idx] = nums[idx-1]; idx--; } nums[idx] = t; } } int main(void) { int N, *nums; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) { scanf("%d", &nums[i]); } insertion_sort(nums, N); for(int i=0; i<N; i++) printf("%d ", nums[i]); printf("\n"); free(nums); return 0; } | cs |
[내용]
idx를 1부터 N-1까지 실행하며, 해당 인덱스에 있는 숫자를 그 앞쪽에서 맞는 위치에 삽입해준다.
[특징]
- 다른 정렬 알고리즘들에 비해서빠른 편이다.
- 정렬해야 할 숫자의 개수가 적은 경우에 유용하다.
Indirection을 이용한 Insertion Sort (삽입 정렬)
[예시 코드]
#include <cstdio> #include <cstdlib> using namespace std; void insertion_sort(int *nums, int *idx, int N) { int t, tIdx; for(int i=0; i<N; i++) idx[i] = i; for(int i=1; i<N; i++) { t = idx[i]; tIdx = i; while(nums[idx[tIdx-1]] > nums[t] && tIdx > 0) { idx[tIdx] = idx[tIdx-1]; tIdx--; } idx[tIdx] = t; } } int main(void) { int N, *nums, *idx; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); idx = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) { scanf("%d", &nums[i]); } insertion_sort(nums, idx, N); for(int i=0; i<N; i++) printf("%d ", nums[idx[i]]); printf("\n"); free(nums); free(idx); return 0; } | cs |
[내용]
- Insertion Sort에서 값을 하나씩 복사시키지 않고, 인덱스용 배열을 따로 생성하고 인덱스만 정렬한다.
[특징]
- 원래 값이 있는 배열은 자료가 변하지 않고 그대로 유지된다.
- sorting된 순서대로 접근하려면, 인덱스 배열을 순서대로 접근하며 이를 인덱스로 사용하여 숫자 배열을 사용하면 된다.
Shell Sort (쉘 정렬)
[예시 코드]
#include <cstdio> #include <cstdlib> using namespace std; void shell_sort(int *nums, int N) { int v, k; for(int h = N/2; h>0; h/=2) { for(int i=0; i<h; i++) { for(int j=i+h; j<N; j+=h) { v = nums[j]; k = j; while(k > h-1 && nums[k-h] > v) { nums[k] = nums[k-h]; k -= h; } nums[k] = v; } } } } int main(void) { int N, *nums; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) scanf("%d", &nums[i]); shell_sort(nums, N); for(int i=0; i<N; i++) printf("%d ", nums[i]); printf("\n"); free(nums); return 0; } | cs |
[내용]
- 기본적인 접근법은 insertion sort와 동일하다.
- h는 스텝 사이즈이다.
- 처음부터 2개씩 비교를 하는 것이 아니라, 스텝 사이즈만큼 떨어트려서 있는 것들끼리만 비교하여 insertion sort 방식으로 정렬을 하고, 스텝 사이즈를 줄이며 이를 반복한다.
[특징]
- 정렬하려는 숫자의 개수와 관계 없이 속도가 빠른 편이다.
- 추가적인 메모리가 필요하지 않다.
Quick Sort (퀵 정렬)
#include <cstdio> #include <cstdlib> void quick_sort(int *nums, int N) { int i, j, v, temp; if(N > 1) { v = nums[N-1]; // Pivot i = -1; j = N-1; while(true) { while(nums[++i] < v); while(nums[--j] > v); if(i >= j) break; temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } temp = nums[i]; nums[i] = nums[N-1]; nums[N-1] = temp; quick_sort(nums, i); quick_sort(nums+i+1, N-i-1); } } int main(void) { int N, *nums; scanf("%d", &N); nums = (int*)malloc(sizeof(int)*N); for(int i=0; i<N; i++) scanf("%d", &nums[i]); quick_sort(nums, N); for(int i=0; i<N; i++) printf("%d ", nums[i]); printf("\n"); free(nums); return 0; } | cs |
[내용]
- quick sort는 나눠서 정렬하는 것이다.
- 인덱스 i는 왼쪽에서 오른쪽으로, 인덱스 j는 오른쪽에서 왼쪽으로 이동한다.
- 우선, 현재 주어진 숫자 배열의 범위에서 가장 오른쪽에 있는 값을 pivot으로 설정한다.
- 인덱스 i를 오른쪽으로 이동하며 가장 먼저 나오는 pivot보다 큰 값의 인덱스까지 이동한다.
- 인덱스 j는 왼쪽으로 이동하며 가장 먼저 나오는 pivot보다 작은 값의 인덱스까지 이동한다.
- 만약에 i가 j의 오른쪽에 있다면 (i와 j가 이동하다가 서로 지나쳤다면) 그만하고, 그렇지 않으면 계속하여 i와 j를 구해서 서로 값을 바꿔준다.
- 이렇게 하면 현재 i가 있는 곳을 기준으로 왼쪽은 pivot보다 작은 값들이, 오른쪽은 pivot보다 큰 값들이 위치하게 된다.
- recursion으로 현재 i보다 왼쪽과 오른쪽을 각각 한번씩 호출해준다.
- 다 끝나고나면 정렬이 된다.
- cf. recursion termination 조건은 if(N > 1)이다. (N이 1이 되면 종료)
[특이 사항]
- 이미 정렬된 경우에는 별로 좋지 않기 때문에 pivot을 랜덤으로 지정해주는 방법도 있다.
- 간격이 클 때는 quick sort를 사용하고, 작으면 insertion sort를 사용하여 병행하는 방법도 있다.
'C & C++ > Reference' 카테고리의 다른 글
| C/C++ - 파일 입출력 (0) | 2018.04.05 |
|---|---|
| C++ string 정리 (3) | 2018.01.23 |