순차 탐색 알고리즘과 이진 탐색 알고리즘을 구현한 후에 둘의 성능 차이를 확인해 봅시다.
#include <iostream> #include <string> #include <time.h> #include <stdlib.h> using namespace std;
먼저 순차 탐색을 구현합시다.
int *sequentailsearch(int *base, size_t n, int value)
{
//순차적으로 배열의 각 요소와 검색할 자료를 비교하세요.
for(size_t s = 0; s<n; s++)
{
if(base[s] == value)
{
//같은 값을 발견하면 해당 위치를 반환합니다.
return base+s;
}
}
//모든 요소와 비교해도 같은 자료가 없으면 0을 반환하세요.
return 0;
}
이번에는 이진 탐색을 구현합시다.
int *binarysearch(int *base, size_t n, int value)
{
//배열의 크기가 0보다 작거나 같으면 재귀 함수를 탈출합니다.
if(n<=0)
{
return 0;
}
//배열의 중간에 있는 요소와 비교합니다.
int gap = base[n/2] - value;
if(gap == 0)
{
//차이가 없으면 배열의 중간에 있는 요소가 있는 위치를 반환하세요.
return base + n/2;
}
if(gap>0)
{
//검색할 자료가 작으면 gap은 0보다 큽니다.
//이때는 배열의 앞쪽에서 검색합니다.
return binarysearch(base,n/2,value);
}
//그렇지 않으면 배열의 뒤쪽에서 검색합니다.
return binarysearch(base+n/2+1, n-n/2-1,value);
}
순차 탐색과 이진 탐색의 성능을 테스트하는 코드를 작성합시다.
int main()
{
//충분히 큰 배열을 선언하세요.
int arr[100000];
srand((unsigned)time(0));//랜덤 시드 값 설정
//이진 탐색은 선행 조건이 정렬 상태여야 한다는 것이죠.
//다음처럼 정렬 상태로 배열의 요소를 설정하세요.
for(int i = 0; i<100000;i++)
{
arr[i] = i*5+rand()%5;
}
//테스트는 100 개의 요소 중에서 탐색하는 것과 10만 개의 요소 중에서 탐색하는 것을 비교할게요.
//탐색에 걸리는 시간이 짧아 테스트를 만 번 하는데 걸리는 시간으로 비교해 보기로 해요.
//먼저 순차 탐색으로 100 개의 요소 중에 탐색하는 것을 만 번 수행하세요.
clock_t st,et;
st = clock();
for(int tc = 0; tc<10000; tc++)
{
int index = rand()%100;
sequentailsearch(arr,100,arr[index]);
}
et = clock();
//수행에 걸린 시간을 출력하세요.
cout<<"100 개에서 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;
//순차 탐색으로 10만 개 요소 중에 탐색하는 것을 만 번 수행하세요.
st = clock();
for(int tc = 0; tc<10000; tc++)
{
int index = rand()%100000;
sequentailsearch(arr,100000,arr[index]);
}
et = clock();
//수행에 걸린 시간을 출력하세요.
cout<<"10만 개 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;
//이진 탐색으로 100개의 요소 중에 탐색하는 것을 만 번 수행하세요.
st = clock();
for(int tc = 0; tc<10000; tc++)
{
int index = rand()%100;
binarysearch(arr,100,arr[index]);
}
et = clock();
//수행에 걸린 시간을 출력하세요.
cout<<"100 개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;
//이진 탐색으로 10만 개의 요소 중에 탐색하는 것을 만 번 수행하세요.
st = clock();
for(int tc = 0; tc<10000; tc++)
{
int index = rand()%100000;
binarysearch(arr,100000,arr[index]);
}
et = clock();
//수행에 걸린 시간을 출력하세요.
cout<<"10만 개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;
return 0;
}
▷ 실행 결과
100 개에서 순차 탐색으로 10000번 수행에 걸린 시간:3 10만 개 순차 탐색으로 10000번 수행에 걸린 시간:782 100 개에서 이진 탐색으로 10000번 수행에 걸린 시간:4 10만 개에서 이진 탐색으로 10000번 수행에 걸린 시간:10
실험에서 순차 탐색은 자료의 수를 1000배 늘렸을 때 250배 정도 걸렸는데 이진 탐색은 2.5배 정도 걸렸습니다. 이처럼 이진 탐색은 자료의 개수가 많이 늘어나도 실제 수행 속도는 크게 늘지 않음을 알 수 있습니다. 수행 속도가 O(logn)이기 때문입니다.