JUINTINATION
정렬(Sort) 본문
반응형
정렬이란?
- 데이터를 기준에 따라 오름차순이나 내림차순으로 나열하는 것
정렬 알고리즘의 평가 기준
- 비교 횟수의 많고 적음
- 이동 횟수의 많고 적음
- 안정성(동일한 키 값을 갖는 원소들의 상대적인 위치가 정렬 후에도 바뀌지 않으면 안정적인 정렬)
선택정렬(Selection Sort)
아래의 과정을 반복하는 정렬
- 주어진 리스트에서 현재 위치 ~ 마지막 위치에서의 최솟값을 찾는다.
- 1에서 찾은 최솟값을 현재 위치의 값과 교환한다.
- 현재 위치를 마지막 위치가 될 때까지 한 칸씩 뒤로 옮긴다.
비교 횟수
- (n - 1) + (n - 2) + … + 1 = n(n - 1)/2 = O(𝑛^2)
이동 횟수
- 3(n - 1)
전체 시간적 복잡도
- O(n^2)
안정성
- 안전성을 만족하지 않음
#define swap(x, y, t) (t = x, x = y, y = t)
void selection_sort(int arr[], int n) {
int tmp;
for (int i = 0; i < n - 1; i++) {
int idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[idx]) idx = j;
}
swap(arr[i], arr[idx], tmp);
}
}#define swap(x, y, t) (t = x, x = y, y = t)
int movement, comparison, tmp;
void selection_sort(int arr[], int n) {
movement = 0, comparison = 0; // 이동횟수와 비교횟수를 구하기 위해 0으로 초기화
for (int i = 0; i < n - 1; i++) {
int idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[idx]) idx = j;
comparison++; // 비교횟수 1 증가
}
swap(arr[i], arr[idx], tmp);
movement += 3; // 이동횟수 3 증가(t = x, x = y, y = t)
}
}삽입정렬(Insertion Sort)
아래의 과정을 반복하는 정렬
- 현재 위치의 값과 앞에 있는 값들을 비교한다.
- 앞에 있는 값보다 현재 위치의 값이 작으면 교환한다.
- 현재 위치를 마지막 위치가 될 때까지 한 칸씩 뒤로 옮긴다.
비교 횟수
- 최선의 경우, O(n) : 이미 정렬되어 있는 경우
- 최악의 경우, O(n^2) : 역순으로 정렬되어 있는 경우
이동 횟수
- 최선의 경우, n - 1
- 최악의 경우, O(𝑛^2)
전체 시간적 복잡도
- 평균의 경우, O(n^2)
안정성
- 안정성을 만족
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
while(j >= 0 && target < a[j]) {
a[j + 1] = a[j];
j--;
}
arr[j + 1] = key;
}
}int movement, comparison;
void insertion_sort(int arr[], int n) {
movement = 0, comparison = 0; // 이동횟수와 비교횟수를 구하기 위해 0으로 초기화
for (int i = 1; i < n; i++) {
int key = arr[i], j = i - 1;
movement++; // 이동횟수 1 증가(key = arr[i])
do {
if (arr[j] > key) {
arr[j + 1] = arr[j];
movement++; // 이동횟수 1 증가
}
comparison++; // 위에서 비교횟수 1 증가
} while (j-- > 0 && arr[j] > key);
arr[j + 1] = key;
movement++; // 이동횟수 1 증가(arr[j + 1] = key)
}
}버블정렬(Bubble Sort)
아래의 과정을 반복하는 정렬
- 현재 위치의 값과 바로 뒤에 있는 값을 비교한다.
- 현재 원소가 다음 원소보다 크면 원소를 교환한다.
- 현재 위치를 마지막 위치가 될 때까지 한 칸씩 뒤로 옮긴다.
비교 횟수
- n(n - 1)/2 = O(n^2)
이동 횟수
- 최선의 경우, 0
- 최악의 경우, 3 * 비교 횟수
- 평균의 경우, O(𝑛^2)
전체 시간적 복잡도
- 평균의 경우, O(𝑛^2)
안정성
- 안정성을 만족
#define swap(x, y, t) (t = x, x = y, y = t)
void bubble_sort(int arr[], int n) {
int tmp;
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}#define swap(x, y, t) (t = x, x = y, y = t)
int movement, comparison, tmp;
void bubble_sort(int arr[], int n) {
movement = 0, comparison = 0; // 이동횟수와 비교횟수를 구하기 위해 0으로 초기화
for (int i = n - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
comparison++; // 비교횟수 1 증가
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1], tmp);
movement += 3; // 이동횟수 3 증가(t = x, x = y, y = t)
}
}
}
}합병(병합)정렬(Merge Sort)
리스트를 균등한 크기로 분할하고 분할된 부분 리스트를 정렬, 정렬된 부분 리스트들을 합하여 전체 리스트를 정렬
- 분할(Divide): 배열을 같은 크기의 2개의 부분 배열로 분할.
- 정복(Conquer): 부분배열을 정렬한다.
부분배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할정복기법 적용 - 결합(Combine): 정렬된 부분 배열을 하나의 배열에 통합.
비교 횟수
- 크기 n인 리스트를 정확히 균등 분배하므로 log(n) 개의 패스
- 각 패스에서 리스트의 모든 레코드 n개를 비교하므로 n번의 비교 연산
- 총 비교 횟수: n*log(n)
이동 횟수
- 레코드의 이동이 각 패스에서 2n번 발생하므로 전체 레코드의 이동은 2n*log(n)번 발생
- 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비 초래
- 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 매우 효율적
전체 시간적 복잡도
- 최적, 평균, 최악의 경우 큰 차이 없이 O(n*log(n))
안정성
- 안정성을 만족
int* sorted;
void merge(int arr[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
else sorted[k++] = arr[j++];
}
if (i > mid) {
for (int l = j; l <= right; l++) {
sorted[k++] = arr[l];
}
}
else {
for (int l = i; l <= mid; l++) {
sorted[k++] = arr[l];
}
}
for (int l = left; l <= right; l++) {
arr[l] = sorted[l];
}
}
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}#include <stdio.h>
#define MAX_SIZE 7
int sorted[MAX_SIZE];
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
void merge(int arr[], int left, int mid, int right) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) sorted[k++] = arr[i++];
else sorted[k++] = arr[j++];
}
if (i > mid) {
for (int l = j; l <= right; l++) {
sorted[k++] = arr[l];
}
}
else {
for (int l = i; l <= mid; l++) {
sorted[k++] = arr[l];
}
}
for (int l = left; l <= right; l++) {
arr[l] = sorted[l];
}
}
int cnt = 1;
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
printf("Pass %d: ", cnt++);
print_array(arr, MAX_SIZE);
}
}
main() {
int arr[MAX_SIZE] = { 4,8,6,3,9,7,2 };
print_array(arr, MAX_SIZE);
merge_sort(arr, 0, MAX_SIZE - 1);
print_array(arr, MAX_SIZE);
}
/*
4 8 6 3 9 7 2
Pass 1: 4 8 6 3 9 7 2
Pass 2: 4 8 3 6 9 7 2
Pass 3: 3 4 6 8 9 7 2
Pass 4: 3 4 6 8 7 9 2
Pass 5: 3 4 6 8 2 7 9
Pass 6: 2 3 4 6 7 8 9
2 3 4 6 7 8 9
*/퀵정렬(Quick Sort)
리스트를 2개의 부분 리스트로 비균등 분할하고, 각각의 부분 리스트를 다시 퀵정렬함(재귀 호출)
- 리스트에서 하나의 원소인 피벗을 고른다.
- 피벗의 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
- 2에서 찾은 두 원소의 위치를 바꾼다.
- 왼쪽과 오른쪽의 탐색 위치가 엇갈리지 않을 때까지 2번부터의 과정을 반복한다.
- 엇갈린 위치를 기준으로 분할된 두 개의 부분 리스트에 대해 크기가 0이나 1이 될 때까지 재귀적으로 위의 과정을 반복한 뒤 인접한 부분 리스트끼리 합친다.
비교 횟수
- 최선의 경우(거의 균등한 리스트로 분할되는 경우), nlog(n)
- 최악의 경우(극도로 불균등한 리스트로 분할되는 경우), n^2
이동 횟수
- 비교 횟수에 비해 적으므로 무시 가능
전체 시간적 복잡도
- 최악의 경우, O(n^2)
- 최적, 평균의 경우, O(n*log(n))
안정성
- 안전성을 만족하지 않음
#define swap(x, y, t) (t = x, x = y, y = t)
int partition(int arr[], int left, int right) {
int tmp, pivot = arr[left];
int low = left, high = right + 1;
do {
do {
low++;
} while (low <= right && arr[low] < pivot);
do {
high--;
} while (high >= left && arr[high] > pivot);
if (low < high) swap(arr[low], arr[high], tmp);
} while (low < high);
swap(arr[left], arr[high], tmp);
return high;
}
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int q = partition(arr, left, right);
quick_sort(arr, left, q - 1);
quick_sort(arr, q + 1, right);
}
}#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 7
#define swap(x, y, t) (t = x, x = y, y = t)
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int partition(int arr[], int left, int right) {
int tmp, pivot = arr[left];
int low = left, high = right + 1;
do {
do {
low++;
} while (low <= right && arr[low] < pivot);
do {
high--;
} while (high >= left && arr[high] > pivot);
if (low < high) {
swap(arr[low], arr[high], tmp);
}
} while (low < high);
swap(arr[left], arr[high], tmp);
return high;
}
int cnt = 1;
void quick_sort(int arr[], int left, int right) {
if (left < right) {
int q = partition(arr, left, right);
printf("pass %d: ", cnt++);
print_array(arr, MAX_SIZE);
quick_sort(arr, left, q - 1);
quick_sort(arr, q + 1, right);
}
}
main() {
int arr[MAX_SIZE] = { 4,8,6,3,9,7,2 };
print_array(arr, MAX_SIZE);
quick_sort(arr, 0, MAX_SIZE - 1);
print_array(arr, MAX_SIZE);
}
/*
4 8 6 3 9 7 2
pass 1: 3 2 4 6 9 7 8
pass 2: 2 3 4 6 9 7 8
pass 3: 2 3 4 6 9 7 8
pass 4: 2 3 4 6 8 7 9
pass 5: 2 3 4 6 7 8 9
2 3 4 6 7 8 9
*/중간값(medium)을 피벗으로 선택하면 불균등 분할 완화 가능
#define swap(x, y, t) (t = x, x = y, y = t)
void quickSort(int arr[], int left, int right) {
int i = left, j = right, pivot = arr[(left + right) / 2], tmp;
do {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j], tmp);
i++;
j--;
}
} while (i <= j);
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}정렬 알고리즘 비교
728x90
'자료구조 및 알고리즘' 카테고리의 다른 글
| 깊이우선탐색(DFS)과 너비우선탐색(BFS) (2) | 2023.01.15 |
|---|---|
| 동적 계획법(dynamic programming) (0) | 2022.07.16 |
| 덱(Deque) (0) | 2022.07.01 |
| 큐(Queue) (0) | 2022.07.01 |
| 스택(Stack) (0) | 2022.07.01 |
Comments