[C언어] quick sort

C언어에서 내장 함수로 제공하는 qsort는 네 개의 매개변수 입력이 있어야 한다.

//void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
qsort(my_elem_list, elem_list_size, sizeof(ELEMENT), myCmpfun);

base: 리스트의 주소
nitems: 정렬하려고 하는 리스트의 크기
size: 정렬하려고 하는 구조체/자료형의 크기
(*compar): 크기 비교 함수

크기 비교 함수는 다음과 같이 구현할 수 있다.
(in non-Decreasing Order)

int myCmpfun(const void* a, const void* b) {
    ELEMENT* elemA = (ELEMENT*)a;
    ELEMENT* elemB = (ELEMENT*)b;

    return (elemA->score - elemB->score);
}

내장함수 qsort()로 1000만 개의 데이터를 정렬하면 5000ms 정도가 걸린다.

source code:

#pragma once
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define MAX_ARRAY_SIZE 100
#define MAX_FNAME_SIZE 100

typedef struct {
    unsigned int score;
    float data[3];
    char comments[16];
}ELEMENT;


typedef int _Cmpfun(const void*, const void*);

void init_elem_list(ELEMENT* , int);
void swap_elem(void*, void*);
void print_elem_list(ELEMENT*, int);

//For Time Check---------------------
#include <Windows.h>
__int64 start, freq, end;
#define CHECK_TIME_START QueryPerformanceFrequency((LARGE_INTEGER*)&freq); QueryPerformanceCounter((LARGE_INTEGER*)&start)
#define CHECK_TIME_END(a) QueryPerformanceCounter((LARGE_INTEGER*)&end); a = (float)((float)(end - start) / (freq / 1000.0f))
float compute_time;
//---------------------For Time Check


int main() {
    char fname_sorted[MAX_FNAME_SIZE], fname_unsorted[MAX_FNAME_SIZE], func_char[4], elem_list_char[10];
    int func_number = -1, elem_list_size = 0;        //func number = -1 for error detection
    ELEMENT* my_elem_list;

    /*---All Files Have to be in the Same Folder---*/
    FILE *fp;
    FILE *f_sorted, *f_unsorted;                    


    //For Time Check---------------------
    CHECK_TIME_START;
    //---------------------For Time Check


    /*---Read File---*/
    fp = fopen("s.txt", "r");

    /*if read file fails*/
    if (fp == NULL) {
        perror("Error Reading File");
        exit(EXIT_FAILURE);
    }

    /*if successful, read lines*/
    fgets(func_char, 4, fp);
    fgets(elem_list_char, 10, fp);
    fgets(fname_unsorted, MAX_FNAME_SIZE, fp);
    fgets(fname_sorted, MAX_FNAME_SIZE, fp);

    /*char to int*/
    func_number = atoi(func_char);
    elem_list_size = atoi(elem_list_char);

    /*---Init List---*/
    my_elem_list = (ELEMENT*)malloc(sizeof(ELEMENT) * elem_list_size);
    init_elem_list(my_elem_list, elem_list_size);

    /*---Run QSort By Case Number---*/
    switch (func_number) {
    case -1: /*Error*/
        perror("Error Reading File");
        exit(EXIT_FAILURE);
        break;

    case 1: /*qsort()*/
        qsort(my_elem_list, elem_list_size, sizeof(ELEMENT), myCmpfun);
        break;

    }

    print_elem_list(my_elem_list, elem_list_size);


    return 0;
}

int myCmpfun(const void* a, const void* b) {
    ELEMENT* elemA = (ELEMENT*)a;
    ELEMENT* elemB = (ELEMENT*)b;

    return (elemA->score - elemB->score);
}

typedef int
_Cmpfun(const void*, const void*);
void qsort_median_insert(void* my_elem_list, size_t list_size, size_t elem_size, _Cmpfun* myCmpfun) {
    ELEMENT* elem_list = (ELEMENT*)my_elem_list;
    ELEMENT elem_pivot;
    int left, right;

    /*Setting pivot, left, right elements*/
    elem_pivot = elem_list[0];
    left = 0;
    right = list_size;
}

void init_elem_list(ELEMENT* list, int list_size) {
    int j;
    for (int i = 0; i < list_size; i++) 
        list[i].score = i + 1;

    //Fisher-Yates Shuffle Algorithm
    srand((unsigned int)time(NULL));

    for (int i = list_size - 1; i >= 1; i--) {
        j = rand() % (i + 1);
        swap_elem(&list[j].score, &list[i].score);
    }
}

void print_elem_list(ELEMENT* list, int list_size) {
    for (int i = 0; i < list_size; i++)
        printf("%d ", list[i].score);
}

void swap_elem(void* a, void* b) {
    ELEMENT* temp;
    temp = (ELEMENT*)b;
    b = (ELEMENT*)a;
    a = temp;
}