반응형
01 4
02 2
03 3
04 3
05
(1)
7 | 4 | 9 | 6 | 3 | 8 | 7 | 5 |
3 | 4 | 9 | 6 | 7 | 8 | 7 | 5 |
3 | 4 | 5 | 6 | 7 | 8 | 7 | 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 | 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 |
3 | 4 | 7 | 5 | 7 | 8 | 9 | 6 |
3 | 4 | 7 | 5 | 7 | 6 | 9 | 8 |
3 | 4 | 5 | 6 | 7 | 7 | 8 | 9 |
06
(1)
71 | 49 | 92 | 55 | 38 | 82 | 72 | 53 |
49 | 55 | 38 | 53 | 71 | 92 | 82 | 72 |
38 | 49 | 55 | 53 | 71 | 82 | 72 | 92 |
38 | 49 | 55 | 53 | 71 | 72 | 82 | 92 |
38 | 49 | 53 | 55 | 71 | 72 | 82 | 92 |
(2)
71 | 49 | 92 | 55 | 38 | 82 | 72 | 53 |
49 | 71 | 55 | 92 | 38 | 82 | 53 | 72 |
49 | 55 | 71 | 92 | 38 | 53 | 72 | 82 |
38 | 49 | 53 | 55 | 71 | 72 | 82 | 92 |
(3) SKIP
07
(1)
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
(2)
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8]
08
int partition(int list[],int left, int right){
int pivot, temp;
int low, high;
low = left;
high = right +1; // 아래 do-while문에서 한 칸씩 이동해야하기 때문
pivot = list[left];
do{
do{
low++;
}while(list[low]<pivot);
do{
high--;
}while(list[high]>pivot);
for (int i = 0; i < n; i++) // 패스 과정 출력
printf("%d ", list[i]);
printf("\nlow=%d, high=%d\n", low, high);
if(low<high) SWAP(list[low],list[high],temp);
}while(low<high);
SWAP(list[left],list[high],temp);
// pivot과 high인덱스에 위치한 요소를 교환
return high;
}
09
(2) 선택 정렬 , (3) 히프 정렬
10
(2) 어느 정도 정렬이 되어 있다.
11
(a) 5 3 4 5 8 9 6 7
(b) 4
(c) 변경되지 않는다. 피봇값을 기준으로 왼쪽 리스트와 오른쪽 리스트 내부에서 순환호출 하기 때문
(d) quick_sort(list,0,2), quick_sort(list,4,7)
12
210 | 220 | 123 | 003 | 513 | 294 | 398 | 528 | 409 | 129 |
003 | 409 | 210 | 513 | 220 | 123 | 528 | 129 | 294 | 398 |
003 | 123 | 129 | 210 | 220 | 294 | 398 | 409 | 513 | 528 |
13
typedef struct{
int key;
char name[30];
}record;
void insertion_sort(record list[], int n){
int i, j;
record r;
for(i=1; i<n; i++){
r = list[i];
for(j=i-1;j>=0&&list[j].key>r.key;j--){
list[j+1]= list[j];
}
list[j+1] = r;
}
}
14
void insertion_sort(int list[], int n){
int i, j, key, m;
for(i=1; i<n; i++){
key = list[i];
for(j=i-1;j>=0&&list[j]>key;j--){
list[j+1] = list[j];
}
list[j+1] = key;
for(m =0; m<i;m++){
printf("%d ",list[m]);
}
printf(" ");
for(m=i; m<n;m++){
printf("%d ",list[m]);
}
printf("\n");
}
}
15
void insertion_sort(ListNode** head) {
ListNode *sorted = NULL;
ListNode *current = *head;
while(current !=NULL){
ListNode* next = current->link;
if(sorted == NULL || sorted->data >current->data){
current->link = sorted;
sorted = current;
}
else{
ListNode* pointer = sorted;
while(pointer->link !=NULL && pointer->link->data < current->data){
pointer = pointer->link;
}
current->link = pointer->link;
pointer->link = current;
}
current = next;
}
*head = sorted;
}
16
void selection_sort(int list[],int n){
int i,j,least,temp,m;
for(i=0;i<n-1;i++){
least = i;
for(j=i+1;j<n;j++){
if(list[j]<list[least]) least =j;
}
SWAP(list[i],list[least],temp);
for(m =0; m<i;m++){
printf("%d ",list[m]);
}
printf(" ");
for(m =i;m<n;m++){
printf("%d ",list[m]);
}
printf("\n");
}
}
17
void quick_sort(int list[],int left, int right){
if(left<right){
int q = partition(list,left,right);
printf("quick_sort(%d,%d)\n",left,right);
quick_sort(list,left,q-1);
printf("quick_sort(%d,%d)\n",left,right);
quick_sort(list,q+1,right);
}
}
18
int middle = (left+right)/2;
if(list[left]<list[right]){
if(list[middle]>list[right]){
pivot = list[right];
}
else{
if(list[left]<list[middle]){
pivot= list[middle];
}
else{
pivot = list[left];
}
}
}
else{
if(list[middle]>list[left]){
pivot = list[left];
}
else{
if(list[right]<list[middle]){
pivot= list[middle];
}
else{
pivot = list[right];
}
}
}
19
void merge_sort(int list[],int left, int right){
int mid;
if(left<right){
mid = (left + right) / 2;
printf("merge_sort(%d,%d)\n",left,right);
merge_sort(list,left,mid);
printf("merge_sort(%d,%d)\n",left,right);
merge_sort(list,mid+1,right);
merge(list,left,mid, right);
}
}
20 , 21 SKIP
'CS > Data Structure' 카테고리의 다른 글
[C언어로 쉽게 풀어쓴 자료구조] Chapter13. 탐색 (2) (2) | 2024.01.13 |
---|---|
[C언어로 쉽게 풀어쓴 자료구조] Chapter13. 탐색 (1) (1) | 2024.01.08 |
[C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (2) (0) | 2024.01.04 |
[C언어로 쉽게 풀어쓴 자료구조] Chapter12. 정렬 (1) (1) | 2023.12.19 |
[C언어로 쉽게 풀어쓴 자료구조] 연습문제 11강 (1) | 2023.12.17 |