[알고리즘] 과제 2. 1000만개 데이터 삽입 정렬 시 걸리는 시간

/*
 2020-03-19 우희은
 삽입정렬 알고리즘
*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

int buffer[10000000]; // 전역 변수로 넣어야 stack overflow가 나지 않음

void fileOpen() {
    FILE *fp = fopen("d://algorithm/unsorted10000000.txt", "r");
    int i = 0;
    int tmp = 0;
    if (fp == NULL) {
        printf("파일을 열 수 없습니다.\n");
    }
    while (fscanf(fp, "%d ", &tmp)!=EOF) {
        buffer[i++] = tmp;
    }

    fclose(fp);
}

void insertSorting(int a) {
    int size = 0;
    int key,i,j;
    for (i= 1; i < a; i++) {
        key = buffer[i];

        for (j = i - 1; j >= 0 && buffer[j] > key; j--) {
            buffer[j + 1] = buffer[j];
        }

        buffer[j + 1] = key;
    }
}

int calHash(int index_start, int index_end) {
    int sum = 0;
    for (int i = index_start; i < index_end+1; i++) {
        sum += buffer[i] - (int)((int)(buffer[i] * pow(10, -5)) * pow(10, 5));
    }
    sum -= (int)((int)(sum * pow(10, -5)) * pow(10, 5));
    return sum;
}

int main() {
    printf("알고리즘 과제 2\n");
    printf("              컴퓨터과학부 2017920038 우희은\n");
    printf("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ\n");
    time_t start, end;
    int n = 10000000; // 계산할 수의 범위

    /* 시간 측정 */
    start = time(NULL); 
    struct tm tm = *localtime(&start);
    printf("start: %d-%d-%d %d:%d:%d\n\n",
        tm.tm_year + 1900, tm.tm_mon + 1, tm.tm_mday,
        tm.tm_hour, tm.tm_min, tm.tm_sec);

    printf("- 컴퓨터 CPU : Intel(R) Core(TM) i7-7500U CPU\n");
    printf("- 메모리 : 8GB\n");
    /* 파일 데이터 불러오기 */
    fileOpen();

    /* 삽입 정렬 */
    insertSorting(n);

    end = time(NULL);
    printf("- 동작시간: %lfms\n", (double)(end - start));

    /* hash 계산 */
    printf("- hash value: %d\n",calHash(4999999,5000099));

    tm = *localtime(&end);
    printf("end: %d-%d-%d %d:%d:%d\n\n",
        tm.tm_year + 1900, tm.tm_mon + 1, tm.tm_mday,
        tm.tm_hour, tm.tm_min, tm.tm_sec);

    return 0;
}

소요시간

데이터를 파일에서 받아오는데 10초 정도 소요되었고, 전체 코드 수행시간은 15097000ms, 즉 251분이 소요되었다.

=> 사진에서는 결과가 잘못 출력되었음

hash 값은 500만번째 요소 ~ 500만 100번째 요소까지 101개의 합을 아래 5자리만 이용하여 표현한 것이다.

컴퓨터 사양

컴퓨터 CPU : Intel(R) Core(TM) i7-7500U CPU @ 2.70Ghz

메모리 : 8GB