C로 시작하는 컴퓨터 프로그래밍4판 - 13장 실전예제(데이터 정렬 프로그램)

01. 데이터 정렬 프로그램

 - 정렬 알고림즘 성능 비교하기

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX_NUM 10000

void Select_Sort(int* a, int count);
void Bubble_Sort(int* a, int count);
void Insert_Sort(int* a, int count);
void Shell_Sort(int* a, int count);
void Quick_Sort(int* a, int count);

// 난수 발생 함수
void Rand_Date(int* a);
int Random(int start, int end);

// 속도 비교 함수
void Check_Speed(int num, char* str, int* a, int count);

int main(void) {
    int date[MAX_NUM];
    int i;

    char* str[] = { "Select", "Bubble", "Insert", "Shell", "Quick" };

    Rand_Date(date);

    for (i = 0; i < 5; i++)
        Check_Speed(i, str[i], date, MAX_NUM);

    return 0;
}

void Select_Sort(int* a, int count) {
    int i, j;
    int min_value, min_index;

    for (i = 0; i < count; i++) {
        min_index = i;
        min_value = a[i];

        for (j = i + 1; j < count; j++) {
            if (min_value > a[j]) {
                min_index = j;
                min_value = a[j];
            }
        }
        a[min_index] = a[i];
        a[i] = min_value;
    }
}

void Bubble_Sort(int* a, int count) {
    int i, j;
    int temp;

    for (i = 0; i < count - 1; i++) {
        for (j = 1; j < count - i; j++) {
            if (a[j - 1] > a[j]) {
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
            }
        }
    }
}

void Insert_Sort(int* a, int count) {
    int i, j;
    int temp;

    for (i = 1; i < count; i++) {
        temp = a[i];
        j = i;
        while ((a[j - 1] > temp) && (j > 0)) {
            a[j] = a[j - 1];
            j = j - 1;
        }
        a[j] = temp;
    }
}

void Shell_Sort(int* a, int count) {
    int i, j, inc, h;
    int temp;

    for (h = count / 2; h > 0; h /= 2) {
        for (i = 0; i < h; i++) {
            for (j = i + h; j < count; j += h) {
                temp = a[j];
                inc = j;
                while (inc > h - 1 && a[inc - h] > temp) {
                    a[inc] = a[inc - h];
                    inc = inc - h;
                }
                a[inc] = temp;
            }
        }
    }
}

void Quick_Sort(int* a, int count) {
    int i, j;
    int v, temp;

    if (count > 1) {
        v = a[count - 1];
        i = -1;
        j = count - 1;
        for (; ; ) {
            while (a[++i] < v);
            while (a[--j] > v);
            if (i >= j) break;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        temp = a[i];
        a[i] = a[count - 1];
        a[count - 1] = temp;
        Quick_Sort(a, i);
        Quick_Sort(a + i + 1, count - i - 1);
    }
}

void Rand_Date(int* a) {
    int i;
    srand((unsigned)time(NULL));
    for (i = 0; i < MAX_NUM; i++) {
        a[i] = Random(1, MAX_NUM);
    }
}

int Random(int start, int end) {
    int rnd = 0;
    rnd = rand() & (end - start) + start;
    return rnd;
}

void Check_Speed(int num, char* str, int* a, int count) {
    clock_t start, end;
    int temp[MAX_NUM];
    int i;
    for (i = 0; i < count; i++) {
        temp[i] = a[i];
    }
    start = clock();

    switch (num) {
    case 0:
        Select_Sort(temp, count);
        break;
    case 1:
        Bubble_Sort(temp, count);
        break;
    case 2:
        Insert_Sort(temp, count);
        break;
    case 3:
        Shell_Sort(temp, count);
        break;
    case 4:
        Quick_Sort(temp, count);
        break;
    }
    end = clock();
    printf("%10s의 수행 시간은 %5ld입니다.\n", str, end - start);
}