반응형
Sort Algorithm Compare
- 시험 방법
정렬 알고리즘들을 500~550개(랜덤)의 값을 만들어 정렬하는 것을 5000번 반복한 시간을 측정하였다.
qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
4029 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
3190 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
2257 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
361 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
236 ms
- 랜덤한 값들을 정렬할 경우 알고리즘별로 시간 측정 결과 대략적으로 다음과 같은 순서로 성능이 좋았다. 퀵소트 이름이 괜히 퀵이 아니다.
- quick > merge > insertion > bubble > selection
- 위 결과는 정렬할 대상의 상태(값 배열)에 따라 달라질 수 있다.
#include <iostream>
#include <vector>
#include <ctime>
#include <chrono>
void selection_sort(int arr[], int size) {
for(int i = 0 ; i < size - 1 ; i++)
for (int j = i + 1 ; j < size ; j++)
if(arr[i] > arr[j]) {
// swap(arr[i], arr[j]);
int t = arr[i] ;
arr[i] = arr[j] ;
arr[j] = t ;
}
}
void bubble_sort(int a[], int n){
int i, j, t;
for (i = 0; i < n - 1; i++) {
int bchanged=0 ;
for (j = 1; j < n - i; j++) // j=(1,10)
{
if (a[j - 1] > a[j]){
t = a[j - 1];
a[j - 1] = a[j];
a[j] = t;
bchanged=1 ;
}
}
if (bchanged==0) break ;
}
}
void insertion_sort(int arr[], int size) {
for(int i = 1 ; i <= size - 1 ; i++)
for (int j = i-1 ; j >= 0 ; j--)
if(arr[j] > arr[j+1]) {
// swap(arr[j], arr[j+1]);
int t = arr[j] ;
arr[j] = arr[j+1] ;
arr[j+1] = t ;
}
else
continue;
}
void merge_sort(int arr[], int size) {
// std::cout << "merge_sort size=" << size << std::endl ;
if (size > 2) {
// 왼쪽 반, 오른쪽 반을 나누어 반복.
merge_sort(arr, size / 2);
merge_sort(arr + size / 2, size - size / 2);
// 왼쪽, 오른쪽 반이 각각 정렬된 상태임. merge한다.
int leftCursor = 0;
int rightCursor = size / 2;
//int buff[50];
int *buff = new int[size] ;
int buffCursor = 0;
// 두 그룹을 각각 스캐닝하면서 순서대로 기록. (어느 한쪽이 끝날때까지)
while (leftCursor < size / 2 && rightCursor < size) {
if (arr[leftCursor] < arr[rightCursor]) {
buff[buffCursor++] = arr[leftCursor++];
} else {
buff[buffCursor++] = arr[rightCursor++];
}
}
// 남은 한 그룹의 데이터를 append
for (int i = leftCursor ; i < size / 2 ; i++)
buff[buffCursor++] = arr[i];
for (int j = rightCursor ; j < size ; j++)
buff[buffCursor++] = arr[j];
memcpy(arr, buff, size * sizeof(int));
delete[] buff ;
} else { // 원소 개수가 2개 이하인 경우, 비교하여 정렬한다.
if (arr[0] > arr[1]) {
// swap(arr[0], arr[1]);
int tmp = arr[0] ;
arr[0] = arr[1] ;
arr[1] = tmp ;
}
}
}
// a: 정렬할 데이터 array
// n: 데이터 개수
void quick_sort(int a[], int n){
int v, t;
int i, j;
if (n > 1){
v = a[n - 1]; // v=축값. 마지막 노드값을 사용
i = -1;
j = n - 1;
while (1){ // 분할
// while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지? -> 없다면??? 없을수는 없다. 자신끼리 비교가 마지막.
while (a[++i]<v) {
// std::cout << "debug : i=" << i << std::endl ;
}
// while (a[--j] > v); // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range???
while( a[--j]>v) {
// std::cout << "debug : j=" << j << std::endl ;
// minus index로 갔는데 에러가 발생하지 않았지만, 쓸데없는 오버로드다. 다른 언어였으면 indexerror이다.
if (j==0) // 전체 검색 완료이므로 더 이상 할 필요없다.
break ;
}
if (i >= j)
break; // i와 j의 위치가 뒤바뀌었으면 분할 끝. 좌우 분할이 이미 잘되어 있다.
// i와 j의 위치가 좌, 우 상태 그대로 라면
t = a[i]; // 두 값을 바꿈.
a[i] = a[j];
a[j] = t;
}
// 피봇이 들어갈 자리는? 왼쪽을 기준으로 정렬이 다 된 상태에서 마지막 i자리에 큰 값이 와 있다.
t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
a[i] = a[n - 1];
a[n - 1] = t;
// i위치 기준으로 좌우 대소 분할 완료.
quick_sort(a, i); // 왼쪽 구간 퀵정렬. (i개만 한다. 즉, i위치는 개수에 포함 안함.)
quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬 (index로 치면 a+i+1부터 a+n-1. 따라서 개수는 a+n-1 - (a+i+1)+1 )
}
}
void print_array(int *a, int n) {
for(int i=0; i<n; i++)
{
std::cout << a[i] << " " ;
}
std::cout << std::endl ;
}
int check_asc(int *a, int n) {
if (n<=1) return 1 ;
for (int i=1; i<n; i++) {
if (a[i-1]>a[i])
return 0 ;
}
return 1 ;
}
int test_alg(void (*pfunc)(int[], int)) {
int cnt = std::rand()%50+500 ;
int *a = new int[cnt] ;
int bcheck=0 ;
if (true) {
// 랜덤값 생성
for (int i=0; i<cnt; i++) {
a[i]= std::rand()%1000 ;
}
} else {
// 이미 정렬된 상태값 생성
for (int i=0; i<cnt; i++) {
a[i]= i ;
}
}
// print_array(a,cnt) ; // 정렬 전.
// (*pfunc)(a, cnt) ; // 이렇게 해도 가능.
pfunc(a,cnt) ;
// print_array(a,cnt) ; // 정렬 후.
bcheck = check_asc(a,cnt) ;
delete[] a ;
return bcheck ;
}
uint64_t getmilli() {
using namespace std::chrono;
return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count() ;
}
int main() {
std::cout << "sort test" << std::endl ;
std::srand(std::time(NULL)) ;
// int a[] = {3,8,5,1,9,4,2,6,7, 10} ;
// int a[10] ;
// for (int i=0; i<10; i++) {
// a[i] = std::rand()%50 ;
// }
// int n = sizeof(a)/sizeof(int) ;
// print_array(a, n) ;
// quick_sort(a, n) ;
// merge_sort(a, n) ;
// bubble_sort(a, n) ;
// print_array(a, n) ;
// return 0 ;
int bcheck=0 ;
int okcnt = 0, failcnt=0 ;
uint64_t ts, te ;
const char *pfunc_name[] = { "selection_sort", "bubble_sort", "insertion_sort", "merge_sort", "quick_sort", NULL} ;
void(*pfunc[])(int[], int) = { selection_sort, bubble_sort, insertion_sort, merge_sort, quick_sort, NULL };
int pfunc_cnt = sizeof(pfunc) / sizeof(pfunc[0]) ;
for (int kk=0; kk<pfunc_cnt; kk++) {
okcnt=0 ;
failcnt=0 ;
if (pfunc[kk]==NULL)
break ;
std::cout << "ALG=" << pfunc_name[kk] << std::endl ;
ts = getmilli() ;
for (int i=0; i<5000; i++) {
bcheck = test_alg(pfunc[kk]) ;
if (bcheck) {
okcnt++ ;
// std::cout << "OK" << std::endl ;
} else {
failcnt++ ;
// std::cout << "FAIL" << std::endl ;
}
}
te = getmilli() ;
std::cout << "OK cnt=" << okcnt << " FAIL cnt=" << failcnt << std::endl ;
std::cout << te-ts << " ms" << std::endl ;
}
return 0 ;
}
만약 이미 정렬된 상태를 다시 정렬을 시키면?
qsort test
ALG=selection_sort
OK cnt=5000 FAIL cnt=0
1507 ms
ALG=bubble_sort
OK cnt=5000 FAIL cnt=0
16 ms
ALG=insertion_sort
OK cnt=5000 FAIL cnt=0
1439 ms
ALG=merge_sort
OK cnt=5000 FAIL cnt=0
164 ms
ALG=quick_sort
OK cnt=5000 FAIL cnt=0
1329 ms
- 위 경우, bubble, merge가 성능이 좋았다. bubble이 좋았던 이유는 바로 이미 정렬되어 있는지를 처음 루프에서 알아낼 수 있기 때문에 그 조건으로 루프 탈출이 가능하기 때문이다.
- 위 조건은 quick 소트 입장에서는 worst case이다. 먼저 이미 정렬되었는지 검사하는 루틴을 추가한다면 이런 경우를 방지할 수 있을 것이다.
Author: crazyj7@gmail.com
'Develop > C&CPP' 카테고리의 다른 글
| [알고리즘] 정렬5: quick sort (0) | 2019.12.15 |
|---|---|
| [알고리즘] 정렬4: merge sort (0) | 2019.12.15 |
| [알고리즘] 정렬3: Insertion sort (0) | 2019.12.15 |
| [알고리즘] 정렬2: bubble sort (0) | 2019.12.13 |
| [알고리즘] 정렬1: selection sort (0) | 2019.12.13 |