수다닷컴

Edit 프랑켄님~ 답글 넘 감사드려요^_^
n은 0, 10, 20, 30 ..... 1000까지만 가고
n 각각에 대해 time이 출력됩니다~
일단 SelectionSort1.c는 n과 time간의 그래프를 그려보면 n^2 그래프 형태가 나온다네요(책에선...)
출력결과는 아래와 같아요~

하지만 SelectionSort2.c는 time이 모두 0초가 나옵니다..프로그램 자체가 논리적으론 정확해도 재려는 시간이 너무 짧기 때문이라고 합니다.. 똑딱거리는 측정에 플러스 1 또는 마이너스 1의 오류가 있기 때문에 정렬 시간이 한 번 똑딱거리는 시간보다 훨씬 길 때만 정확한 결과를 반환한다고 해요~ 여기까진 이해는 가지만 그래프는 어찌 그려야 할지 모르겠습니다ㅜ_ㅜ

Analysis와 Measurement 둘다 말해주어야 분석방법이 잘 되는건데, 그럼 , Analysis는 n과 time 사이의 관계, 즉 그래프로 나타내주어야 한다는 건가요? Measurement는 이 출력결과만 보여주면 충분한건가요?----------------------------------------------------------------------------------------
SelectionSort1.c를 점근적으로 분석하면 처음 for문 실행되고 do-while 의 for문이 실행되므로
총 for 문이 두개이니까 θ(n^2)인가요?

그리고 SelectionSort2.c를 점근적으로 분석해보면 for 문이 두개니까 θ(n^2) 이렇게 하면 되나요?

점근 분석법을 배웠는데 이해가 잘 안가요ㅜ_ㅜ
책에도 이것에 대해서는 설명이 안 되어 있어서 너무 답답합니다ㅜㅜㅜ
자세히 설명해주시면 정말 감사하겠습니다^_^

아래는 SelectionSort1.c입니다~

#include stdio.h
#include time.h
#include SelectionSort.h
#define MAX_SIZE 1001

void main(void)
{
int i, n, step = 10;
int a[MAX_SIZE];
double duration;
printf( n repetitions time\n);
for(n = 0; n = 1000; n += step)
{
long repetitions = 0;
clock_t start = clock();
do
{
repetitions++;
for(i = 0; i n; i++)
a[i] = n - i;
sort(a, n);
} while(clock() - start 1000);
duration = (double) difftime(stop, start);
duration /= repetitions;
printf(%6d %9d %f\n, n, repetitions, duration);
if(n == 100) step = 100;
}
}다른 .c 파일인데 SelectionSort2.c라고 했습니다~

#include stdio.h
#include time.h
#include Selection.h
#define MAX_SIZE 1001
void main(void)
{
int i, n, step = 10;
int a[MAX_SIZE];
double duration;
clock_t start;
printf(ntime\n);
for(n = 0; n = 1000; n += step)
{
for(i = 0; i n; i++)
a[i] = n - i;
start = clock();
sort(a, n);
duration = ((double) (clock() - start)) / CLOCKS_PER_SEC;
printf(6d%f\n, n, duration);
if(n == 100) step = 100;
}
}

그리고 아래는 SelectionSort1.c와 SelectionSort2.c가 동시에 include 하고 있는 SelectionSort.h에요~
#include stdio.h
#include math.h
#include time.h
#include stdlib.h
#define MAX_SIZE 1001
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))
void sort(int [], int);
void main(void)
{
int i, n;
int list[MAX_SIZE];
printf(Enter the number of numbers of generators : );
scanf(%d, &n);
if( n 1 || n MAX_SIZE) {
fprintf(stderr, Improper value of n\n);
exit(EXIT_FAILURE);
}
for(i = 0; i n; i++) {
list[i] = rand() % 1000;
printf(%d , list[i]);
}
sort(list, n);
printf(\n Sorted array : \n );
for(i = 0; i n; i++)
printf(%d , list[i]);
printf(\n);
}
void sort(int list[], int n)
{
int i, j, min, temp;
for(i = 0; i n-1; i++) {
min = i;
for(j = i+1; j n; j++)
if(list[j] list[min])
min = j;
SWAP(list[i], list[min], temp);
}
}

신청하기