최소값을 찾아서 왼쪽으로 이동시키는데 배열크기만큼 반복하여 정렬하는 방법. 선택정렬의 비교회수는 다음과 같습니다. 선택정렬의 연산시간은 다음과 같습니다. 선택정렬의 장점은 데이터의 양이 적을 때 아주 좋은 성능을 나타냅니다. 데이터의 양이 적을 떄 아주 좋은 성능. 작은 값을 선택하기 위해서 비교는 여러 번 하지만 교환횟수가 적습니다. 선택정렬의 단점. 가장 작은 값과 현재값을 교환하는 방식. 100개 이상의 자료에 대해서는 속도가 떨어져서 적절히 사용되기가 어렵습니다. |
#include <iostream> #include <cstdio> void Select_Sort(int parm_data[], int parm_count) { int min_data = 0, min_index = 0; int i, j; int comparison_count = 0; for (i = 0; i < parm_count - 1; i++) { min_index = i; min_data = parm_data[i]; for (j = i + 1; j < parm_count; j++) { comparison_count++; if (min_data > parm_data[j]) { min_data = parm_data[j]; min_index = j; } } parm_data[min_index] = parm_data[i]; parm_data[i] = min_data; } printf("total comprison_count = [ %d ].", comparison_count); printf("\n\n\n"); } void main() { int array[5] = { 7, 4, 11, 9, 2 }; int i; printf("=== Before ===\n\n"); for (i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); printf("================================"); printf("\n\n"); Select_Sort(array, 5); printf("=== After ===\n\n"); for (i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); } |
버블정렬 |
인접해 있는 두 개의 값을 비교해서 자료 교환을 합니다. 인터체인지, 쉬프팅 소트, 버블 정렬의 비교회수는 동일합니다. 엔마일 부터 시작해서 1까지 입니다. 수학식으로 표현하면 이렇게 되므로 공식은 이것입니다. 버블 정렬의 연산시간은 다음과 같습니다. 인접해 있는 두 개의 값을 비교하여 자료의 위치를 이동시키므로 단순합니다. 여러 차례 값을 비교하므로 안전성 있게 값을 정렬합니다. 버블정렬의 단점은 첫번째 패스에서 자료의 교환이 없었다면 주어진 값은 이미 정렬됩 상태이지만, 최대 마늠 비교회수와 연산시간이 소요됩니다. 다른 정렬에 비해서 연산시간이 오래 걸립니다. 이미 소트가 완료된 경우를 체크하지 못하고 계속 정렬을 시도합니다. 따라서 고려할 수 있도록 소스를 수정하는 것은 각 패스의 시작 시점에서 flag 값을 1로 설정합니다. 자리 바꿈이 일어났다면 flag 값을 0 으로 변경합니다. flag 값이 1 이라는 소리는 한번도 자리바꿈이 일어나지 않았다는 뜻입니다. |
#include <iostream> #include <cstdio> void Bubble_Sort(int parm_data[], int parm_count) { int i, j, temp = 0; int comparison_count = 0; for (i = 0; i < parm_count - 1; i++) { for (j = 0; j < parm_count - 1 - i; j++) { comparison_count++; if (parm_data[j] > parm_data[j + 1]) { temp = parm_data[j]; parm_data[j] = parm_data[j + 1]; parm_data[j + 1] = temp; } } } printf(" total comparison count is [ %d ].", comparison_count); printf("\n\n\n"); } void main() { int array[5] = { 7, 4, 11, 9, 2 }; int i; printf("=== before ===\n\n"); for (i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); printf("================================"); printf("\n\n"); Bubble_Sort(array, 5); printf("=== after ===\n\n"); for (i = 0; i < 5; i++) printf("%d ", array[i]); printf("\n\n"); } |
퀵정렬, 분할 정복법에 근거합니다. 정렬할 리스트를 두개로 분할하고 정렬하는 방법입니다. 축을 기준으로 정렬하는데, 첫번쨰의 데이터를 축값으로 합니다. |
퀵정렬의 경우 비교회수 최선일 경우의 비교회수 공식은 다음과 같고, 최악의 경우의 비교회수는 공식은 다음과 같습니다. 최악일 경우의 비교회수 공식, 최악일 경우의 비교회수 공식, 위의 그림을 제일 처음에는 비교하고 그 다음에는 퀵 정렬의 연산시간 연산시간 공식 엔로그엔 최악의 경우 엔제곱 정렬할 데이터가 이미 준비되어 있고 모든 데이터들을 정렬해야 할 경우에 가장 빠른 수행속도. 축 값이 같은 것끼리는 순서관계가 파괴도비니다. 중요한 데이터의 경우에는 퀵 정렬을 사용하지 안흔ㄴ 것이 좋다. 안전성이 없다. |
알고리즘. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬합니다. 리스트 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피벗이라고 합니다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. |
리스트 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피벗이라고 합니다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눕니다. 이렇게 리스트를 둘로 나는 것을 분할이라고 합니다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않습니다. 분할된 두 개의 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재구니느 리스트의 크기가 0이나 1이 될 때까지 반복됩니다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. |
#include <iostream> #include <cstdio> void quickSort(int arr[], int left, int right) { int i = left, j = right; int pivot = arr[(left + right) / 2]; int temp; do { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } while (i <= j); /* recursion */ if (left < j) quickSort(arr, left, j); if (i < right) quickSort(arr, i, right); } void main() { int array[10] = { 27, 4, 37, 2, 62, 12, 59, 16, 49, 18 }; int i; printf("=== before ===\n\n"); for (i = 0; i < 10; i++) printf("%d ", array[i]); printf("\n\n"); printf("================================"); printf("\n\n"); quickSort(array, 0, 9); printf("=== After ===\n\n"); for (i = 0; i < 10; i++) printf("%d ", array[i]); printf("\n\n"); } |