a book on c 연습문제 풀이 8장

소개글

a book on c 연습문제 풀이 8장에 대한 보고서 자료입니다.

본문내용

*right);
80 ++left;
81 --right;
82 }
83 }
84 return left;
85 }
문제 25.
만일 배열이 적은 원소를 갖고 있다면, 예를 들어 7개 이하, 버블 정렬이나 치환 정렬이 퀵 정렬보다 빨라야 한다. 다음 quicksort() 버전은 이러한 사실을 고려한 것이다.
int quicksort(int *left, int *right)
{
int *p, *q, pivot;
static int cnt = 0;
if (right - left < 7) {
for (p = left; p < right; ++p)
for (q = p + 1; q <= right; ++q)
if (*p > *q)
swap(*p, *q);
}
else if (find_pivot(left, right, &pivot) == yes) {
p = partition(left, right, pivot);
quicksort(left, p - 1);
quicksort(p, right);
}
return ++cnt;
}
변수 cnt의 사용을 주목하여라. 함수를 호출한 곳으로 리턴되는 값은 함수가 호출된 횟수이다. 이 새로운 quicksort()가 과연 빠르게 실행되는지를 실험해 보아라. 실행 시간과 함수가 호출된 횟수 사이에는 상관관계가 있는가?
☞ 위의 코드는 정렬시킬 배열의 원소가 7개 이하일 경우 Bubble Sort를 하는 코드이다. 새로운 quicksort()를 사용하지 않고, 원래의 quicksort()를 사용할 경우 7개의 원소를 정렬하는데 무려 13번 이상의 호출을 한다. 따라서 크기가 작은 데이터를 정렬시킬 경우는 위의 새로운 quicksort()함수가 더 빠를 것으로 보인다. 컴퓨터의 속도가 너무 빨라 데이터의 개수가 7개가되지 않을 경우 정렬시간을 측정할 수는 없는 듯하다. 그러나 함수의 호출 횟수가 적으면 실행 시간이 줄어드는 것은 당연한 듯하다.
문제 26.
퀵 정렬에서 피봇 원소를 잘 찾아내는 알고리즘은 매우 중요하다. 간단한 알고리즘은 배열에서 두 개의 다른 원소를 찾아내어 그중 큰 것을 피봇으로 선택하는 것이다. 이 알고리즘을 사용하면, 퀵 정렬은 배열이 이미 정렬되어 있거나 또는 거의 정렬된 형태일 때 n log n보다는 n2에 비례하는 시간이 걸린다. 이것은 매우 중요한 사실이다. 왜냐하면 실질적으로 배열은 초기에 부분적으로 정렬되어 있는 상태일 경우가 종종 있기 때문이다. 이 알고리즘을 사용하도록 quicksort 코드를 다시 작성하고, 배열이 초기에 정렬된 상태일 때 퀵 정렬이 매우 비효율적임을 증명하는 검사 프로그램을 작성해 보아라. 만일 배열이 역순으로 정렬되어 있다면, 어떻게 되겠는가?
문제 27.
피봇 원소를 찾기 위해, 배열의 세 원소 중에서 하나를 선택하였다. 만일 5개의 원소 중에서 선택한다면, 실행 시간은 어느 정도 줄어들어야 한다. quicksort 코드를 수정하여 이 기법을 구현해 보아라. 이때 적절한 곳에 매크로를 사용해야 한다. 실행 시간의 감소 여부를 검사하는 프로그램을 작성하여라. 피봇을 찾는 최적의 전략은 배열의 자료에 따라 다르다. 5개의 원소 중에서 피봇을 선택하는 것이 일반적인 전략이다. 만일 7개의 원소 중에서 피봇을 선택한다면 어떻게 되겠는가? 이것 또한 시험해 보아라.
문제 28.
a[]는 크기가 100인 정수 배열이고, 각 i에 대해 원소 a[i]는 i 값을 가진다고 가정하자. 만일 quicksort(a, a + 99)로 호출하면, quicksort() 함수는 얼마나 많이 호출되겠는가? find_pivot()의 각 버전에 대해 이 횟수를 계산해 보아라.
☞ 1 #include
2 #include
3 #include "quicksort.c"
4
5 #define N 100
6
7 int main(void)
8 {
9 int array[N];
10 int i, cnt;
11
12 for(i = 0; i < N; i++)
13 array[i] = i;
14
15 for(i = 0; i < N; i++)
16 printf("%3d ", array[i]);
17 putchar('\n');
18
19 printf("Count: %d\n", quicksort(array, array + N - 1));
20
21 for(i = 0; i < N; i++)
22 printf("%3d ", array[i]);
23 putchar('\n');
24 return 0;
25 }
198번 호출된다.
문제 29.
partition()에 의해 리턴되는 포인터는 원래의 배열을 두 부분으로 나누는 데 사용된다. 첫 번째 부분 배열의 크기를 "분할 크기"라고 한다. 난수 발생기를 사용하여 크기가 100인 배열을 채워라. 이 배열에 대한 분할 크기를 구하기 위해 find_pivot()과 partition()을 호출하여라. 이러한 호출을 100번 정도 반복하여 평균 분할 크기를 추적해 보아라. 기대되는 평균 분할 크기는 배열 크기의 반이다. 실험해 본 결과 그렇게 되는가?
☞ 꼭 그렇지는 않은 듯하다. 출력되어지는 분할 크기들은 아주 자유롭다.
1 #include
2 #include
3 #include "quicksort.c"
4 #define N 100
5
6 int main(void)
7 {
8 int a[N];
9 int i, pivot, *p;
10 static int cnt = 0;
11 yes_no tru;
12
13 srand(time(NULL));
14 for(i = 0; i < N; i++) { //100번 배열 채우고, 호출.
15 a[i] = rand() % 100;
16 if (find_pivot(a, a + N - 1, &pivot) == yes) {
17 p = partition(a, a + N - 1, pivot);
18 printf("cnt: %d 분할크기: %d\n ", cnt, p - a);
19 }
20 cnt++;
21 }
22 putchar('\n');
23 return 0;
24 }

키워드

C,   a book on c,   어 북 온 씨,   프로그램,   씨,   연습문제,   풀이