C언어 10만개의 난수를 5가지 정렬 알고리즘(선택, 삽입, 퀵, 힙, 셸)으로 정렬 성능(비교, 교환, 실행시간) 출력

#include "stdafx.h"
/*
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
*/
#define SIZE 20 //배열 크기
#define RUN 1 //실행횟수
 
// 각 정렬 횟수 20개 + 평균값
// 배열하나에 10만개의 랜덤수 삽입
// 랜덤수를 5개의 배열에 넣고
// 각 sort에서 각 배열을 사용
// change, compare, time [20]배열로 만들어 
// while(i < 20)i++; 
 
 
void genNumber(); // 랜덤 생성
void insertionSort(); // 삽입 정렬
void selectionSort(); // 선택 정렬
void quickSort(int left, int right); // 퀵 정렬
void heapSort(); // 힙 정렬
void shellSort(); // 셸 정렬
void init();  //시작
void getAvg();//평균값 구함
void printAvg();//평균값 출력
void print(); // test print
void saveRLog(int times); // 생성된 랜덤넘버 random.txt로 저장
void saveSLog(int times, int type); // 랜덤넘버를 정렬한 숫자들을 각 정렬 이름.txt로 저장
void saveALog(); // 각 정렬 평균 비교 교환 실행시간을 average.txt로 저장
void testing(int arg); // 1~20 오름차순 내림차순 test용
 
clock_t start, end; //시작시간 끝나는 시간
double time_[5][RUN]; // 결과 시간
 
long long N[5][SIZE] = { 0, }; //각 [5]sort에 쓸 값 저장[SIZE]개
long long temp;               //random number generate할때쓰고 swap할때 씀
long long compare[5][RUN] = { 0, };//한번 돌때마다 저장
long long change[5][RUN] = { 0, }; //한번 돌때마다 저장
long long cp = 0, ch = 0;    // 각 sort에서 compare, change 일어날때 ++
long long cp_res[5] = { 0, };//각 정렬 compare평균값 저장
long long ch_res[5] = { 0, };//각 정렬 change평균값 저장
double    time_res[5] = { 0.0 };//각 정렬 실행 시간 평균값 저장
 
int check = 0; // genRandom에서 씀 이미 있는수인지 체크용
int left = 0, right = SIZE - 1;//퀵정렬용 left 0번째, right 맨뒤
 
enum sort { insertion, selection, quick, heap, shell };//배열 index구분용
 
char sort_name[5][20] =
{
    { "INSERTION SORT" },
    { "SELECTION SORT" },
    { "QUICK SORT" },
    { "HEAP SORT" },
    { "SHELL SORT" }
};// 파일저장명을 위함 string
 
int main() {
 
    srand(time(NULL));
    init();       // 모든 정렬 알고리즘 실행
    getAvg();     // 비교, 교환, 소요시간의 평균구함
    saveALog();   // 평균값 저장
    printAvg();   // 콘솔에 비교, 교환, 소요시간 평균 출력 
}
 
void init() {
 
    int i;
 
    for (i = 0; i < RUN; i++) {
 
        printf("generate the numbers...\n");
        genNumber(); // 랜덤넘버
        //testing(1); //0 은 오름차순, 1은 내림차순
 
        saveRLog(i); // 랜덤넘버 저장
        printf("running... %d times\n", i + 1);
 
        start = clock();
        insertionSort();
        end = clock(); 
        time_[insertion][i] = (double)(end - start) / CLOCKS_PER_SEC;
        compare[insertion][i] = cp;
        change[insertion][i] = ch;
        cp = 0, ch = 0;
        saveSLog(i, insertion);
 
        start = clock();
        selectionSort();
        end = clock();
        time_[selection][i] = (double)(end - start) / CLOCKS_PER_SEC;
        compare[selection][i] = cp;
        change[selection][i] = ch;
        cp = 0, ch = 0;
        saveSLog(i, selection);
 
        start = clock();
        printf("quick sorting...\n");
        quickSort(left, right);
        end = clock();
        time_[quick][i] = (double)(end - start) / CLOCKS_PER_SEC;
        compare[quick][i] = cp;
        change[quick][i] = ch;
        cp = 0, ch = 0;
        saveSLog(i, quick);
 
        start = clock();
        printf("heap sorting...\n");
        heapSort();
        end = clock();
        time_[heap][i] = (double)(end - start) / CLOCKS_PER_SEC;
        compare[heap][i] = cp;
        change[heap][i] = ch;
        cp = 0, ch = 0;
        saveSLog(i, heap);
 
        start = clock();
        shellSort();
        end = clock();
        time_[shell][i] = (double)(end - start) / CLOCKS_PER_SEC;
        compare[shell][i] = cp;
        change[shell][i] = ch;
        cp = 0, ch = 0;
        saveSLog(i, shell);
    }
}
 
void getAvg() {
 
    int i = 0, j = 0;
 
    for (i = 0; i < 5; i++) {
 
        for (j = 0; j < RUN; j++) {
 
            cp_res[i] += compare[i][j];
            ch_res[i] += change[i][j];
            time_res[i] += time_[i][j];
        }
 
        cp_res[i] /= RUN;
        ch_res[i] /= RUN;
        time_res[i] /= (double)RUN;
    }
}
 
void printAvg() {
 
    int i;
 
    puts("");
 
    for (i = 0; i < 5; i++) {
 
        printf("%s = 비교: %lld번, 교환: %lld번, time: %.10lf초\n", sort_name[i], cp_res[i], ch_res[i], time_res[i]);
    }
}
 
void insertionSort() { // 삽입 [0]
 
    int i, j, s = 1;
    long long temp;
 
    for (i = 1; i < SIZE; i++)    {
 
        temp = N[insertion][i];
 
        for (j = i - 1; j >= 0 && N[insertion][j] > temp; j--) {
 
            cp++;
            N[insertion][j + 1] = N[insertion][j];
            ch++;
            s = 0;
        }
 
        if (1 != (j >= 0 && N[insertion][j] > temp) && s != 0)
            ch++;
 
        N[insertion][j + 1] = temp;
    }
}
 
void selectionSort() { // 선택 [1]
 
    int i, j;
    long long indexMin, temp;
 
    printf("selection sorting...\n");
 
    for (i = 0; i < SIZE - 1; i++) {
 
        indexMin = i;
 
        for (j = i + 1; j < SIZE; j++) {
 
            cp++;
            //printf("selection cp++: %d\n", cp);
            if (N[selection][j] < N[selection][indexMin]) {
 
                indexMin = j;
            }
        }
 
        if (N[selection][indexMin] != N[selection][i]) {
        
            temp = N[selection][indexMin];
            N[selection][indexMin] = N[selection][i];
            N[selection][i] = temp;
            ch++;
            //printf("selection ch++: %d\n", ch);
        }
    }
}
 
void quickSort(int left, int right) { // 퀵 [2]
 
    int i, j;
    i = left, j = right;
 
    long long pivot = N[quick][(left + right) / 2];
    long long temp = 0;
 
    while (i <= j){
 
        while (N[quick][i] < pivot) {
            cp++;
            i++;
        }
 
        if (N[quick][i] != pivot) {//피벗이랑 같을때 비교X
 
            cp++;
        }
 
        while (N[quick][j] > pivot) {
 
            cp++;
            j--;
        }
        if (N[quick][j] != pivot) {//피벗이랑 같을때 비교X
 
            cp++;
        }
        if (i <= j) {
 
            if (i != j) {
 
                temp = N[quick][i];
                N[quick][i] = N[quick][j];
                N[quick][j] = temp;
                ch++;
            }
 
            i++;
            j--;
        }
 
    } 
 
    if (left < j) {
        quickSort(left, j);
    }
    if (i < right) {
        quickSort(i, right);
    }
}
 
void heapSort(){
 
    for (int i = 1; i < SIZE; i++) {
 
        int c = i;
 
        do {
            int root = (c - 1) / 2;
 
            if (N[heap][root] < N[heap][c]) {
 
                cp++;
 
                long long temp = N[heap][root];
                N[heap][root] = N[heap][c];
                N[heap][c] = temp;
 
                ch++;
            }
 
            c = root;
 
        } while (c != 0);
 
    }
 
    // 크기를 줄여가며 반복적으로 힙을 구성
 
    for (int i = SIZE - 1; i >= 0; i--) {
 
        long long temp = N[heap][0];
        N[heap][0] = N[heap][i];
        N[heap][i] = temp;
 
        int root = 0;
 
        int c = 1;
 
        do {
 
            c = 2 * root + 1;
            // 자식 중에 더 큰 값을 찾기 
            if (c < i - 1 && N[heap][c] < N[heap][c + 1]) {
 
                c++;
                cp++;
            }
 
            // 루트보다 자식이 크다면 교환 
 
            if (c < i && N[heap][root] < N[heap][c]) {
 
                cp++;
                temp = N[heap][root];
                N[heap][root] = N[heap][c];
                N[heap][c] = temp;
                ch++;
            }
 
            root = c;
        } while (c < i);
 
    }
 
}
 
void shellSort() { // h = 3*h + 1 수열 사용
 
    int i, j, k, h;
 
 
    for (h = 1; h < SIZE; h = 3 * h + 1); // n보다 작은 최대의 h를 찾는다.
 
    for (h /= 3; h > 0; h /= 3) { // 최대h의 앞 간격으로 이동
 
        for (i = 0; i < h; i++) {
 
            
            for (j = i + h; j < SIZE; j += h) {
 
                cp++;
                long long v = N[shell][j];
                k = j;
 
                while (k > h - 1 && N[shell][k - h] > v) { //삽입할곳 찾음
                    cp++;
                    N[shell][k] = N[shell][k - h];
                    k -= h;
                    ch++;
                }
 
                N[shell][k] = v;
                
            }
        }
    }
}
 
void genNumber() { // 랜덤수 생성
 
    int i, j;
 
    for (i = 0; i < SIZE; i++) {
        //i~SIZE까지 반복
        while (1) {
 
            //printf("in loop\n");
            temp = ((long long)rand() << 16) | ((long long)rand());
            
 
            j = 0;
            check = 0;
 
            for (j = 0; j <= i; j++) {
 
                if (N[j] != temp) continue;
                //N[j]가 temp가 아니면 계속 실행
                else if (N[j] == temp) {
                    //N[j]가 temp와 같으면 check++하고 for문 break;
                    check++;
                    break;
                }
            }
 
            if (check == 0) {
                //check가 0이면 N[i]에 temp를 삽입하고 while break;
                N[insertion][i] = temp;
                N[selection][i] = temp;
                N[quick][i] = temp;
                N[heap][i] = temp;
                N[shell][i] = temp;
                break;
            }
        }
        //printf("created %d items\n", i + 1);
    }
}
 
void testing(int arg) {
 
    int i, j;
 
    if (arg == 0) {
        printf("arg == 0\n");
        for (i = 0; i < 5; i++) {
 
            for (j = 0; j < SIZE; j++) {
 
                N[i][j] = j;
                printf("%d ", N[i][j]);
            }
            puts("");
        }
    }
 
    if (arg == 1) {
 
        int k = 0;
 
        for (i = 0; i < 5; i++) {
            printf("arg == 1\n");
 
            for (j = SIZE; j > 0; j--) {
 
                N[i][k] = j;
                k++;
                //printf("%d ", N[i][k]);
            }
            puts("");
            k = 0;
        }
        
    }
 
    for (int l = 0; l < 5; l++) {
 
        for (int m = 0; m < SIZE; m++) {
 
            printf("%d ", N[l][m]);
        }
        puts("");
    }
 
    puts("");
}
 
void print() {
 
    int i;
    for (i = 0; i < SIZE; i++)
        printf("i : %lld\n", N[0][i]);
}
 
void saveRLog(int times) { // save the random numbers
 
    FILE *fp;
    int i;
 
    fp = fopen("RANDOM NUMBERS.txt", "a");
 
    fprintf(fp, "\n=======================================================================================\n");
    fprintf(fp, "                                %d TIMES RANDOM NUMBER                                  \n", times + 1);
    fprintf(fp, "=======================================================================================\n");
 
    for (i = 0; i < SIZE; i++) {
 
        fprintf(fp, "%lld\n", N[0][i]);
    }
 
    fclose(fp);
}
 
void saveSLog(int times, int type) { // save the sorting numbers
 
    int i;
    char str[30] = { " " };
 
    FILE *fp;
 
    for (i = 0; i < 30 && sort_name[type][i] != NULL; i++)
        str[i] = sort_name[type][i];
 
    strcat(str, ".txt");
    // sprintf쓰면 되는데 ㅡㅡ
    fp = fopen(str, "a");
 
    fprintf(fp, "\n=======================================================================================\n");
    fprintf(fp, "                                %d TIMES %s                                            \n", times + 1, str);
    fprintf(fp, "=======================================================================================\n\n");
 
    for (i = 0; i < SIZE; i++) {
 
        fprintf(fp, "%lld\n", N[type][i]);
    }
 
    fclose(fp);
}
 
void saveALog() { // save the average numbers
 
    int i, j, k, l, m, n;
 
    FILE *fp;
 
    fp = fopen("AVERAGE.txt", "a");
 
    for (i = 0; i < 5; i++) {
 
        fprintf(fp, "\n=======================================================================================\n");
        fprintf(fp, "                        %s average compare, change, time                                 \n", sort_name[i]);
        fprintf(fp, "=======================================================================================\n\n");
        fprintf(fp, "COMPARE: ");
 
        for (j = 0; j < RUN; j++)
            fprintf(fp, "%lld ", compare[i][j]);
 
 
        fprintf(fp, "\n");
        fprintf(fp, "CHANGE: ");
 
        for (k = 0; k < RUN; k++)
            fprintf(fp, "%lld ", change[i][k]);
 
        fprintf(fp, "\n");
        fprintf(fp, "TIME: ");
 
        for (l = 0; l < RUN; l++)
            fprintf(fp, "%.5lf ", time_[i][l]);
 
        fprintf(fp, "\n");
        
        fprintf(fp, "AVERAGE = 비교: %lld번, 교환: %lld번, time: %.5lf초\n", cp_res[i], ch_res[i], time_res[i]);
        fprintf(fp, "\n");
    }
}

RUN: 5가지 정렬 알고리즘의 실행 횟수

SIZE: 배열의 크기

5가지 정렬 알고리즘의 비교 교환 실행시간, 난수들, 각 정렬로 정렬된 정수들을 프로젝트 폴더에 .txt파일로 저장

프로젝트 설정 -> 고급 -> C코드로 컴파일