[ Algorithms ] 04. 고급 정렬 알고리즘 (병합/퀵/힙/특수/계수/기수 정렬)

2023.03 ~ 2023.06

 

 

 

 

 

 

 

 

 

************* 실습 **************

실습1 #include <stdio.h> #include <stdlib.h> #include <time.h> #define _CRT_SECURE_NO_WARNINGS     void quicksort(int arr[], int p, int r); int partition(int arr[], int p, int r); void print(int arr[], int n);   int main(void) {         int n;         scanf_s("%d", &n);           srand((unsigned int)time(NULL));                //랜덤변수 초기화         int* randnum;                                                        //포인터 변수 선언         randnum = (int*)malloc(sizeof(int) * n);  //랜덤수 넣을 배열 크기 동적할당         for (int i = 0; i < n; i++) {                randnum[i] = (int)rand() / (double)RAND_MAX * 1000;       //발생시킨 랜덤값을 randomnum 배열에 넣음         }         print(randnum, n);              //정렬전 데이터 출력         printf("\n");           quicksort(randnum, 0, n - 1);    //퀵정렬 함수 호출         print(randnum, n);              //정렬후 데이터 출력           free(randnum);                 //동적할당된 배열 해제 }       void quicksort(int arr[], int p, int r) {         if (p < r) {                int q = partition(arr, p, r);                quicksort(arr, p, q - 1);                quicksort(arr, q + 1, r);         } }     int partition(int arr[], int p, int r) {         int x = arr[r];         int i = p - 1;         int tmp;         for (int j = p; j <= r - 1; j++) {                if (arr[j] <= x) {                        tmp = arr[++i];                        arr[i] = arr[j];                        arr[j] = tmp;                }         }         tmp = arr[i + 1];         arr[i + 1] = arr[r];         arr[r] = tmp;         return i + 1; }   void print(int arr[], int n) {         for (int i = 0; i < n; i++) {                printf("%d ", arr[i]);         } }

 

 

 

 

 

 

 

 

 

 

 

 

실습 2 #include <stdio.h> #include <stdlib.h> #include <time.h> #define _CRT_SECURE_NO_WARNINGS     void quicksort(int arr[], int p, int r); int partition(int arr[], int p, int r); void print(int arr[], int n);   int main(void) {         int n;         scanf_s("%d", &n);           srand((unsigned int)time(NULL));                //랜덤변수 초기화         int* randnum;                                                        //포인터 변수 선언         randnum = (int*)malloc(sizeof(int) * n);  //랜덤수 넣을 배열 크기 동적할당         for (int i = 0; i < n; i++) {                randnum[i] = (int)rand() / (double)RAND_MAX * 1000;       //발생시킨 랜덤값을 randomnum 배열에 넣음         }         print(randnum, n);              //정렬전 데이터 출력         printf("\n");           quicksort(randnum, 0, n - 1);    //퀵정렬 함수 호출         print(randnum, n);              //정렬후 데이터 출력           free(randnum);                 //동적할당된 배열 해제 }       void quicksort(int arr[], int p, int r) {         if (p < r) {                int q = partition(arr, p, r);                quicksort(arr, p, q - 1);                quicksort(arr, q + 1, r);         } }     int partition(int arr[], int p, int r) {         int x = arr[r];         int i = p - 1;         int tmp;         for (int j = p; j <= r - 1; j++) {                if (arr[j] <= x) {                        tmp = arr[++i];                        arr[i] = arr[j];                        arr[j] = tmp;                }         }         tmp = arr[i + 1];         arr[i + 1] = arr[r];         arr[r] = tmp;         return i + 1; }   void print(int arr[], int n) {         for (int i = 0; i < n; i++) {                printf("%d ", arr[i]);         } }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

실습3 #include <stdio.h> #include <stdlib.h> #include <time.h> #define _CRT_SECURE_NO_WARNINGS     void countingSort(int* arr, int k, int n); void print(int arr[], int n);   int main(void) {         int n; int k;         printf("n: ");  scanf_s("%d", &n);         printf("k: ");  scanf_s("%d", &k);           srand((unsigned int)time(NULL));                //랜덤변수 초기화         int* randnum;                                                        //포인터 변수 선언         randnum = (int*)malloc(sizeof(int) * n);  //랜덤수 넣을 배열 크기 동적할당           for (int i = 0; i < n; i++) {                randnum[i] = (rand() % k) + 1;         }           print(randnum, n);              //정렬전 데이터 출력         printf("\n");           countingSort(randnum, k, n);     //병합정렬 함수 호출         print(randnum, n);              //정렬후 데이터 출력           free(randnum);                 //동적할당된 배열 해제 }     void countingSort(int* arr, int k, int n) {         int i;         int* result; int* grade;         result = (int*)malloc(sizeof(int) * n);         grade = (int*)malloc(sizeof(int) * k);         for (i = 0; i < k; i++)                grade[i] = 0;         for (i = 0; i < n; i++)                grade[arr[i]] = grade[arr[i]] + 1;         for (i = 1; i < k; i++)                grade[i] = grade[i] + grade[i - 1];         for (i = n - 1; i >= 0; i--) {                result[grade[arr[i]] - 1] = arr[i];                grade[arr[i]]--;         }         for (i = 0; i < n; i++)                arr[i] = result[i]; }   void print(int arr[], int n) {         for (int i = 0; i < n; i++) {                printf("%d ", arr[i]);         } }

 

 

 

 

 

 

 

 

 

 

 

************* 과제 **************

04. 고급정렬.pdf

0.73MB

과제1(병합정렬).c

0.00MB

과제2(힙정렬).c

0.00MB

 

 

04 고급정렬2.pdf

0.43MB

과제3.c

0.00MB