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

Quick sort

'알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다.

분할 정복 방법을 통해 구현되는 정렬 방법

시간 복잡도

최악 : O(n^2)

평균 : O(nlogn)

설계를 통해서 개선 가능한 부분

구현 과정

1. pivot을 선택한다.
2. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다.
3. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다.
4. 두 포인터가 가리키는 요소를 교환한다.
5. 2-4를 반복한다.
6. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다.
7. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다.
   1. section의 크기가 0 또는 1이면 그냥 return 한다.

설계를 통한 개선

pivot 선택 과정에서 가장 첫번째 요소를 계속해서 선택해 나간다면 역순으로 배치되었을 때, 최악의 시간복잡도가 나올 수 있다.

따라서 기존 코드에서 중간 요소를 첫번째 요소와 교환하여 사용하는 방법으로 구현함으로써 개선할 수 있다.

다른 nlogn보다 빠른 이유

먼 거리 교환 처리와 캐시 효율

캐시 효율 : 한 번 선택된 기준은 제외

정렬된 값은 제외하고 남은 값만 정렬하면 됨

메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문

메모리

O(log n)만큼의 메모리 필요

불안정 정렬

원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.

큰 수를 다루는 퀵소트 구현

/*
2020-03-26 우희은
퀵정렬 알고리즘
*/

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

typedef struct _MY_OBJ {
    int s, e;
}obj;

int buffer[10000000]; // 전역 변수로 넣어야 stack overflow가 나지 않음//
obj obj_arr[10000000];//
obj tmp_arr[10000000];//
int index = 0;


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 swap(int a, int b) { 
// swap을 쓰면 stack over flow가 나와서 그냥 직접 바꾸는 식으로 바꾸었다.
    int tmp = buffer[a];
    buffer[a] = buffer[b];
    buffer[b] = tmp;
}
*/
void QuickSorting(int left, int right) {
    srand((unsigned int)time(NULL));
    int pivot_index = rand() % 9999999 + 1; //
    int tmp;
    int start, end;
    // 랜덤으로 pick한 pivot 값과 첫번째 값 바꾸기
    tmp = buffer[left];
    buffer[left] = buffer[pivot_index];
    buffer[pivot_index] = tmp;

    obj_arr[index].s = left; obj_arr[index++].e = right;
    do {
        int size = index;
        index = 0;
        for (int i = 0; i < size; i++) {
            left = obj_arr[i].s; right = obj_arr[i].e;

            if (right - left < 4) { // 삽입 정렬이용
                for (int j = left + 1; j < right + 1; j++) {
                    int key = buffer[j];
                    int k;
                    for (k = j - 1; k >= left && buffer[k] > key; k--) {
                        buffer[k + 1] = buffer[k];
                    }
                    buffer[k + 1] = key;
                }
                continue;
            }
            start = left; end = right + 1;
            pivot_index = left + (right - left) / 2;
            tmp = buffer[left];
            buffer[left] = buffer[pivot_index];
            buffer[pivot_index] = tmp;

            do {
                do {
                    start++;
                } while (buffer[start] <= buffer[left] && left <= start);
                do {
                    end--;
                } while (buffer[end] > buffer[left] && right >= end);
                if (start <= end) {
                    tmp = buffer[start];
                    buffer[start] = buffer[end];
                    buffer[end] = tmp;
                }
                else
                    break;
            } while (1);

            if (left != end) {
                tmp = buffer[end];
                buffer[end] = buffer[left];
                buffer[left] = tmp;
            }

            if (end - 1 - left>0) {
                tmp_arr[index].s = left; tmp_arr[index++].e = end - 1;
            }
            if (right - end - 1>0) {
                tmp_arr[index].s = end + 1; tmp_arr[index++].e = right;
            }
        }
        for (int i = 0; i < index; i++) {
            obj_arr[i] = tmp_arr[i];
        }
    } while (index);
}

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");
    clock_t start, end;
    int n = 10000000; // 계산할 수의 범위//

                      /* 파일 데이터 불러오기 */
    fileOpen();

    /* 시간 측정 */
    start = clock(NULL);

    printf("- 컴퓨터 CPU : Intel(R) Core(TM) i7-7500U CPU @ 2.70Ghz \n");
    printf("- 메모리 : 8GB\n");

    /* 삽입 정렬 */
    QuickSorting(0, n - 1);

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

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

    return 0;
}

재귀 함수 실행 시 stackoverflow 이므로 obj 구조체의 배열을 하나 만들어 스택처럼 구현하게 하였고, swap 함수도 stackoverflow를 일으키므로 일일이 다 풀어서 써주었다.

삽입 정렬과의 비교

삽입 정렬 : 15097000ms (251분)

퀵 정렬 : 1016ms (1초)

무려 1500배 차이였다.

컴퓨터 사양

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

메모리 : 8GB