Data Structures in C (C언어로 쉽게 풀어쓴 자료구조) - 천인국 9장 연습문제

Posted by Patchman
2009.05.01 00:32 Univ Study/자료구조와 실습

1. (2), (3) 선택 정렬과 히프정렬은 안정적이지 않다.

2. (3) 멀리 떨어진 요소들을 삽입정렬한다.

3. (2) 어느정도 정렬이 되어 있다.

4. (4) 합병정렬

5. (2) 최선의 경우는 이다 ->최선의 경우에는 이다.

6. (1) 히프정렬을 구현하기 위해서는 포인터를 가진 노드구조가 필요하다.->1차원 배열을 이용하여 구현한다.

7. (2) 합병정렬은 분할하는 과정에서 정렬이 이루어진다.->합병정렬은 합병하는 과정에서 정렬이 이루어진다.

8. (1) 레코드간의 비교만 가능하면 적용할 수 있다.->레코드들을 서로 비교하지 않는다.

9. (2) 선택정렬 -> 하나의 레코드의 크기가 크다면 이동횟수가 적은 정렬 방법이 바람직하다

10.

(1) 선택정렬

(7 4 9 6 3 8 7 5)->

(3 4 9 6 7 8 7 5)->

(3 4 9 6 7 8 7 5)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 8 7 9)->

(3 4 5 6 7 7 8 9)

(3 4 5 6 7 7 8 9)

(2) 삽입정렬

(7 4 9 6 3 8 7 5)->

(4 7 9 6 3 8 7 5)->

(4 7 9 6 3 8 7 5)->

(4 6 7 9 3 8 7 5)->

(3 4 6 7 9 8 7 5)->

*(3 4 6 7 8 9 7 5)->

(3 4 6 7 7 8 9 5)->

(3 4 5 6 7 7 8 9)

(3) 버블정렬

(7 4 9 6 3 8 7 5)->

(4 7 6 3 8 7 5 9)->

(4 6 3 7 7 5 8 9)->

(4 3 6 7 5 7 8 9)->

(3 4 6 5 7 7 8 9)->

(3 4 5 6 7 7 8 9)->

(4) 쉘정렬

(7 4 9 6 3 8 7 5)->

(7 4 5 6 3 8 7 9)->

(6 3 5 7 4 8 7 9)->

(3 4 5 6 7 7 8 9)

11.

(1) 퀵정렬(숫자가 변경되는 경우만 기록)

(71 49 92 55 38 82 72 53)->

(38 49 53 55 71 82 72 92)->

(38 49 53 55 71 72 82 92)

(2) 합병정렬

(71 49 92 55 38 82 72 53)->

(49 71 92 55 38 82 72 53)->

(49 71 55 92 38 82 72 53)->

(49 55 71 92 38 82 72 53)->

(49 55 71 92 38 82 72 53)->

(49 55 71 92 38 82 53 72)->

(38 49 53 55 71 72 82 92) 정렬 완료

(3) 히프정렬

숫자를 하나씩 삽입하여 히프 생성

92

5582

53 38 71 72

49

0

92

55

82

53

38

71

72

49

82

5572

53 38 71 49

92

0

82

55

72

53

38

71

72

92

72

5571

53 38 49 82

92

0

72

55

71

53

38

49

82

92

71

5549

53 38 72 82

92

0

71

55

49

53

38

72

82

92

55

5349

38 71 72 82

92

0

55

53

49

38

71

72

82

92

53

3849

55 71 72 82

92

0

53

38

49

55

71

72

82

92

49

3853

55 71 72 82

92

0

49

38

53

55

71

72

82

92

38

4953

55 71 72 82

92

0

38

49

53

55

71

72

82

92

12. 퀵정렬에서의 피봇 선택 문제

(1) 왼쪽 첫 번째 요소를 피봇으로 하는 경우(노란색은 피봇을 나타냅니다.)

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

(2) 왼쪽, 중간, 오른쪽 가운데 중간(노란색은 피봇을 나타냅니다.)

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

->

1

2

3

4

5

6

7

8

9

13. 퀵정렬

(1) (5 3 4 5 8 9 6 7)

(2) 7번의 비교연산이 수행됨

(3) 피봇값은 이미 정렬된 위치에 있기 때문에 피봇값의 위치는 변경되지 않는다.

(4) quick_sort(list, 0, 2)와 quick_sort(list, 4, 7)

14. 히프 정렬의 불안정성

예를 들어 다음의 2개의 리스트를 정렬하는 경우를 생각해보자.

(1) 99 80(A) 80(B) 70

(2) 99 95 80(A) 80(B)

위의 2개의 리스트는 다음 그림처럼 히프로 생성되고

99

80(A)80(B)

70

99

9580(A)

80(B)

히프정렬을 하면 결과는 다음과 같이 된다.

(1)99 80(A) 80(B) 70

(2)99 95 80(B) 80(A)

즉 같은 값을 갖는 레코드들의 위치가 정렬후에 변경될 수 있다.

15. 기수정렬의 각 단계

* 1단계

QUEUE [0] --- 210 220

QUEUE [1] ---

QUEUE [2] ---

QUEUE [3] --- 123 003 513

QUEUE [4] --- 294

QUEUE [5] ---

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] --- 398 528

QUEUE [9] --- 019 129

210 220 123 003 513 294 398 528 019 129

* 2단계

QUEUE [0] --- 003

QUEUE [1] --- 210 513 019

QUEUE [2] --- 220 123 528 129

QUEUE [3] ---

QUEUE [4] ---

QUEUE [5] ---

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] ---

QUEUE [9] --- 294 398

003 210 513 019 220 123 528 129 294 398

* 3단계

QUEUE [0] --- 003 019

QUEUE [1] --- 123 129

QUEUE [2] --- 210 220 294

QUEUE [3] --- 398

QUEUE [4] ---

QUEUE [5] --- 513 528

QUEUE [6] ---

QUEUE [7] ---

QUEUE [8] ---

QUEUE [9] ---

003 019 123 129 210 220 294 398 513 528

16. 문제를 다음과 같이 보완하여야 합니다.

데이터의 수가 100개일 때 삽입정렬과 퀵정렬이 동일하게 1초에 정렬을 완료하였다. 데이터의 수가 1000,10000,100000,1000000등으로 증가할 때 평균적인 경우에, 두 정렬방법이 필요로 하는 시간을 계산하고 비교하라.

(답)

평균의 경우에 삽입정렬의 이론적인 시간복잡도는 이고 퀵정렬은 이다. 따라서 필요로 하는 연산의 개수는 대략적으로 다음의 표에 비례하여 늘어날 것이 예상된다.

n=100

n=1000

n=10000

n=100000

n=1000000

삽입정렬

연산의 수

수행시간

1초

100초

10000초

퀵정렬

연산의 수

수행시간

1초

약 15초

약 200초

약 2501초

약 30017초

17.

알고리즘 A: 전체 배열을 순차적으로 탐색하므로 항상 의 시간 복잡도를 가진다.

알고리즘 B: 배열을 정렬하기 위하여 사용하는 정렬방법에 따라 시간복잡도가 달라진다. 만약 합병정렬을 사용한다고 가정하면 의 시간이 소요된다.

18. 수정된 삽입정렬 코드

#define MAX_SIZE 100

#define NAME_SIZE 32

typedef struct {

int key;

char name[NAME_SIZE];

} record;

record list[MAX_SIZE];

int n;

//

insertion_sort(record list[], int n)

{

int i, j;

record current_record;

for(i=1; i<n; i++){

current_record = list[i];

for(j=i-1; j>=0 && list[j].key>current_record.key;j--)

list[j+1]=list[j];

list[j+1]=current_record;

}

}

19. 삽입정렬의 각 단계출력

//

insertion_sort(int list[], int n)

{

int i, j, k;

int key;

for(i=1; i<n; i++){

// 정렬된 리스트 출력

printf("(");

for(k=0;k<i;k++)

printf("%d ", list[k]);

printf(")");

// 정렬해야할 리스트 출력

printf("(");

for(k=i;k<n;k++)

printf("%d ", list[k]);

printf(")\n");

key = list[i];

for(j=i-1; j>=0 && list[j]>key;j--)

list[j+1]=list[j];

list[j+1]=key;

}

}

20. 함수 포인터를 이용한 삽입정렬

//

insertion_sort(int list[], int n, int (*f)())

{

int i, j;

int key;

for(i=1; i<n; i++){

key = list[i];

for(j=i-1; j>=0 && f(list[j],key);j--)

list[j+1]=list[j];

list[j+1]=key;

}

}

int ascend(int x, int y)

{

if( x<y ) return 1;

else return 0;

}

int descend(int x, int y)

{

if( x>y ) return 1;

else return 0;

}