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) 왼쪽 첫 번째 요소를 피봇으로 하는 경우(노란색은 피봇을 나타냅니다.)
->
->
->
->
->
->
->
->
(2) 왼쪽, 중간, 오른쪽 가운데 중간(노란색은 피봇을 나타냅니다.)
->
->
->
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;
}
11.해싱(연습문제).hwp