여러가지 C++ 소스 코드를 보면서, 궁금했던 점이 있다.
프로그래밍을 하게되면 정렬을 많이 사용하게 되는데,
여기서 궁금한 점이 하나 생겨나게 된다.
어떤 정렬이 실제 사람에 의해 만들어진 데이터가 입력되었을 때,
평균적으로 좋은 속도를 가지는 가에 대한 것이다.
만약, 데이터의 양이 늘어난다면 매우 악의적인 사용자가 아닌 가정하에서는
대부분 랜덤함수에 의해 데이터가 생성될 것이다.
물론, 데이터의 양이 적을 때에는 정렬의 속도차이가 중요하지 않을 것이다.
그러므로 이 실험에서는 여러가지 전제조건을 정해놓고 시작하기로 하였다.
1. N의 크기는 100만이상이다.
2. 구조체가 아닌, 1차원의 32비트 정수 배열을 정렬한다.
3. 데이터는 랜덤함수에 의해 만들어지며, rand함수를 두번 실행시켜 나온 값을 곱한다.
4. 비교 대상이 되는 정렬함수는 std::sort , std::stable_sort이다.
일단 전제조건 4번에서 qsort를 제외한 이유는
KOI시험장에서 실험 해 본 결과 2배 이상의 차이가 났기 때문이다.
그리하여 결국 이 네가지 기준에 따라 프로그램을 제작하였다.
소스코드 제작에 미흡한점이 있을 수 있습니다. 양해 부탁드립니다.#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>#define N 10000003 // 원하는 N + 3
int data [ N ] ;
int table [ N ] ;int main ( )
{
int i , st , en ;for ( i = 0 ; i < N - 3 ; i ++ )
{
data [ i ] = rand ( ) * rand ( ) ;
}
printf ( "N = %d 의 경우 stable_sort와 sort 비교\n" , N - 3 ) ;memcpy ( table , data , sizeof ( table ) ) ;
st = clock ( ) ;
std :: sort ( data , data + N ) ;
en = clock ( ) ;
printf ( "sort : %d\n" , en - st ) ;
memcpy ( table , data , sizeof ( table ) ) ;st = clock ( ) ;
std :: stable_sort ( data , data + N ) ;
en = clock ( ) ;
printf ( "stable_sort : %d\n" , en - st ) ;return 0 ;
}
이 소스코드로 실험해 본 결과, sort함수와 stable_sort함수의 시간 차이는
데이터의 크기가 커질수록 커지는것 같았다.
속도면에서만 보았을 때, sort함수가 stable_sort함수보다 빠른 것으로 나왔다.
N이 1000만일 경우, 최대 0.5초 이상 차이가 나기도 하였다.
물론 필자는 stable_sort의 특성을 정확하게 모르고 실험을 진행했다.
혹시, stable_sort가 sort보다 더 빠른 속도를 내는 전제조건을 알고 계신분은
댓글을 달아주셔서 필자의 지식을 업그레이드(...) 시켜주셨으면 합니다.
이미 전제조건에서부터 참가자격을 박탈당한 qsort의 경우도, 마찬가지로 부탁드립니다.
일단, 많이 쓰이는 부분에서 이러한 속도차이를 낸 이유를 모르겠다.
요즘 소스코드를 보면 stable_sort가 더 많이 쓰이는 것 같기도 한데..
이에 대해 정확한 지식을 갖고 계신분은 포스팅을 하시어 트랙백을 달아주시거나,
댓글에 많은 정보를 기록해 주셨으면 합니다.
