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

정보통신공학 학부 공부 기록/알고리즘 (Algorithms)

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

hanol02 2023. 8. 14. 13:55

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]);
        }
}