[알고리즘] 합병정렬과 퀵정렬(2) - 예제

[문제1] n개의 양의 정수(중복 가능)를 입력받아 합병정렬하는 프로그램

- 단일연결리스트로 구현

입력예시                                 출력예시

8  73 65 48 31 29 20 8 3

3 8 20 29 31 48 65 73

#include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *next; }; void partition(struct node *L, struct node **L1, struct node **L2, int n) { struct node *p = L; *L1 = L; for (int i = 0; i < (n / 2) - 1; i++) { p = p->next; } *L2 = p->next; p->next = NULL; } struct node *merge(struct node **L1, struct node **L2){ struct node *p, *L; struct node *A = *L1; struct node *B = *L2; if (A->data <= B->data){ L = A; A = A->next; p = L; } else{ L = B; B = B->next; p = L; } while ((A != NULL) && (B != NULL)){ if (A->data <= B->data){ p->next = A; A = A->next; p = p->next; } else{ p->next = B; B = B->next; p = p->next; } } while (A != NULL){ p->next = A; p = A; A = A->next; } while (B != NULL){ p->next = B; p = B; B = B->next; } return L; } void mergeSort(struct node **L, int n){ struct node *L1, *L2, *p = *L; if (n > 1){ partition(p, &L1, &L2, n); if ((n % 2) == 0){ mergeSort(&L1, n / 2); mergeSort(&L2, n / 2); } else{ mergeSort(&L1, n / 2); mergeSort(&L2, (n / 2) + 1); } *L = merge(&L1, &L2); } } void addList(struct node **L, int value) { struct node *p = *L; struct node *newnode = (struct node*)malloc(sizeof(struct node)); newnode->data = value; newnode->next = NULL; if (*L == NULL) { *L = newnode; } else { while (p->next != NULL) { p = p->next; } p->next = newnode; } } void printList(struct node *L) { struct node *p = L; while (p != NULL) { printf(" %d", p->data); p = p->next; } printf("\n"); } void deleteList(struct node *L) { struct node *p = L; while (p != NULL) { L = L->next; free(p); p = L; } } void main(){ int n, value; struct node *L = NULL; scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", &value); addList(&L, value); } mergeSort(&L, n); printList(L); deleteList(L); }

[문제2] n개의 양의 정수(중복 가능)를 입력받아 퀵정렬하는 프로그램

- 배열로 구현

입력예시                               출력예시

8  73 65 48 31 29 20 8 3

3 8 20 29 31 48 65 73

#include <stdio.h> #include <stdlib.h> #include <time.h> int findPivotIndex(int *L, int l, int r){ int randomValue1, randomValue2, randomValue3; if (r - l <= 1){ return l; } srand((unsigned)time(NULL)); randomValue1 = (rand() % (r - l)) + l; randomValue2 = (rand() % (r - l)) + l; randomValue3 = (rand() % (r - l)) + l; if ((L[randomValue1] >= L[randomValue2] && L[randomValue1] <= L[randomValue3]) || (L[randomValue1] <= L[randomValue2] && L[randomValue1] >= L[randomValue3])) { return randomValue1; } else if (((L[randomValue2] >= L[randomValue1]) && (L[randomValue2] <= L[randomValue3])) || ((L[randomValue2] <= L[randomValue1]) && (L[randomValue2] >= L[randomValue3]))) { return randomValue2; } else { return randomValue3; } } int inPlacePartition(int *L, int l, int r, int k){ int temp, i = l, j = r - 1, p = L[k]; temp = L[k]; L[k] = L[r]; L[r] = temp; while (i <= j){ while (i <= j && L[i] < p) { i = i + 1; } while (j >= i && L[j] >= p) { j = j - 1; } if (i < j){ temp = L[i]; L[i] = L[j]; L[j] = temp; } } temp = L[i]; L[i] = L[r]; L[r] = temp; j = r - 1; while (i <= j){ while (i <= j && L[i] == p) { j = j - 1; } if (i < j && L[i] == p){ temp = L[i]; L[i++] = L[j]; L[j] = temp; } } return i; } void inPlaceQuickSort(int *L, int l, int r){ int k, a, b, c; k = findPivotIndex(L, l, r); c = b = inPlacePartition(L, l, r, k); if (l >= r) { return; } while (1){ if (L[c] != L[b]){ a = c + 1; break; } c--; } inPlaceQuickSort(L, l, a - 1); inPlaceQuickSort(L, b + 1, r); } void printList(int *L, int n) { for (int i = 0; i < n; i++) { printf(" %d", L[i]); } } void main(){ int *L, n; scanf("%d", &n); L = (int*)malloc(sizeof(int)*n); for (int i = 0; i < n; i++){ scanf("%d", &L[i]); } inPlaceQuickSort(L, 0, n - 1); printList(L, n); free(L); }