Murra Blog

정렬 알고리즘의 실행시간 비교

• Exchange sort, Merge sort, Quick sort 알고리즘을 구현하기.

• 각각의 정렬 방법에서 key를 비교한 횟수와 실행시간을 측정하여 비교한다. 측정에는 clock 함수를 쓴다.

• Exchange sort와 Quick sort의 비교는 key의 갯수가 다른 3가지 오름차순으로 정렬된 데이터를 생성해여 비교한다.

• Merge sort와 Quick sort의 비교는 key의 갯수가 다른 3가지 경우에 대해 각각 5개의 임의의 데이터를 생성하여 평균값으로 비교한다.

• key의 갯수는 실행시간이 충분한 유효숫자를 가질 수 있도록 각자 정한다.

• 측정된 key의 비교횟수와 실행시간이 정렬 알고리즘들의 이론적 시간 복잡도와 일치하는지 분석한다.

• 입력 형식
  input.txt, 처음은 오름차순 데이터, 그 다음은 임의의 데이터가 입력된다.

• 출력 형식

  

• Exchange Sort : for문을 중첩하여 선택된 인덱스의 키와 나머지 키를 비교하여 선택된 키보다 작으면 앞으로 가게 한다.(인접한 원소끼리 비교하여 작은 게 앞으로 오게 한다.) 시간 복잡도가 O(N^2)이다.

• Merge Sort : 정렬되지 않은 배열을 반으로 나눈다. 길이가 1이 될 때 까지 나눈 후, 나눈 것을 다시 합친다. 합칠 때 작은 원소 순서대로 오게 한다. 시간 복잡도가 O(NlogN)이다.

• Quick Sort : 한 원소를 pivot으로 잡는다. 배열의 맨 왼쪽 원소를 left, 오른쪽 인덱스를 right라고 하고, left부터 오른쪽으로 옮겨가며 pivot보다 큰 값이 나올때까지, right부터 왼쪽으로 옮겨가며 pivot보다 작은 값이 나올때까지 이동한다. 두 원소를 교환한다. left가 right보다 오른쪽에 있으면 다시 왼쪽 오른쪽으로 나눠진 배열을 다시 퀵 정렬한다. 시간 복잡도가 최악의 경우에 O(N^2), 평균 O(NlogN)이 나온다.

Exchange Sort와 Quick Sort의 비교 (오름차순으로 정렬된 데이터)

• N값(key의 개수)에 10000, 20000, 40000을 넣어 수행한다.
  

• Exchange sort의 경우 이론적 시간 복잡도가 O(N^2) 이므로 N이 2배 늘어날때마다 시간이 4배 늘어날 것으로 예상이 된다.

  N=10000 일때 0.09375, N=20000일 때 0.359375, N=40000일 때 1.515625가 걸렸다.

  0.09375 : 0.359375 = 1 : 3.83333 이므로 거의 1:4 이고, 0.09375 : 1.515625= 1:16.1666667 이므로 거의 1:16이다.

  0.359375 : 1.515625= 1 : 4.217391 로 거의 1:4이다.

  clock의 오차를 감안하면 exchange sort의 시간 복잡도가 O(N^2)인 것을 알 수 있다. 이론적 시간 복잡도와 일치한다.

  key 값의 비교 횟수도 역시 49995000: 199990000 : 799980000 = 1 : 4 : 16의 꼴을 띈다.

• Quick Sort는 정렬된 데이터가 들어갔을 때 최악의 경우로 O(N^2)이 걸린다.

  그러므로 N값이 2배 늘어날때마다 시간이 4배 늘어날 것으로 예상이 된다.

  N=10000일 때 0.078125, N=20000일 때 0.328125, N=40000일 때 1.3125가 걸렸다.

  0.078125 : 0.328125 = 1 : 4.2 로 거의 1:4 이고, 0.078125 : 1.3125 = 1 : 16.8 로 거의 1:16이다.

  0.328125 : 1.3125 = 1 : 4이다.

  clock의 오차를 감안하면 Quick Sort는 정렬된 데이터가 들어갔을 때 최악으로 O(N^2)이 걸린다는 것을 알 수 있다.

  key 값의 비교 횟수도 역시 49995000: 199990000 : 799980000 = 1 : 4 : 16의 꼴을 띈다.

  (N)^2: (2N)^2 : (4N)^2 = 1 : 4 : 16

Merge Sort와 Quick Sort의 비교 (무작위 데이터, 5번 수행 후 평균값)

• N값(key의 개수)이 1000000, 2000000, 4000000을 넣어 수행한다.
  

• Merge Sort의 경우 이론적 시간 복잡도가 O(NlogN)이다. N값이 2배 늘어날 때 마다 약 2.~배 정도 늘어날 것으로 예상이 된다.

  N=1000000일 때 0.23125, N=2000000일 때 0.48125, N=4000000일 때 0.95625가 걸렸다.

  0.23125 : 0.48125 = 1 : 2.081081, 0.23125 : 0.95625 = 1 : 4.135135, 0.48125 : 0.95625 = 1 : 1.987013 으로, clock의 오차를 감안하면 예상된 시간 복잡도와 비슷하다.

  key 값의 비교 횟수는 19951424 : 41902848 : 87805696 = 1 : 2.1 : 4.4 로 2배 보다 약간 더 늘어났다.

• Quick Sort의 경우 평균적으로 O(NlogN)의 시간 복잡도를 가진다. N값이 2배 늘어날때마다 2.~배 늘어날 것으로 예상이 된다.

  N=1000000일 때 0.031250, N=2000000일 때 0.065625, N=4000000일 때 0.131250가 걸렸다.

  0.031250 : 0.065625 = 1 : 2.1, 0.065625 : 0.131250 = 1 : 2, 0.031250 : 0.13125 = 1 : 4.2 이므로 clock의 오차와 평균을 구할 때 5번 밖에 수행하지 않아 오차가 클 수 있다는 점을 감안하면 예상된 시간 복잡도와 일치한다.

  key 값의 비교 횟수는 4088134 : 8475511 : 17790888 = 1 : 2.07319 : 4.351835로 N값이 2배 늘어날 때마다 2배보다 약간 더 늘어났다.

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <vector>
using namespace std;
char ex[] = "Exchange Sort";  // 13
char qu[] = "Quick Sort";     // 10
char me[] = "Merge Sort";     // 10
char kc[] = "Key Compares";   // 12
char et[] = "Exe.Time";       // 8
char sp[] = "             ";  // 13

unsigned long long key_compare; // 비교횟수 count
unsigned long long result[2][3];  // 1번 key_compare 저장
unsigned long long result2[2][3];  // 2번 key_compare 저장
double ti[2][3];   // 1번 시간 저장
double ti2[2][3];   // 2번 시간 저장

int in[3];         // 1번 N 값 저장
int in2[3];         // 2번 N 값 저장

void init() { key_compare = 0; }
void exchange_sort(unsigned long long * v, int size);
void merge(unsigned long long * v, int low, int mid, int high);
void mergesort(unsigned long long * v, int low, int high);
void quick_sort(unsigned long long *v, int left, int right);

int main() {
    int n;
    ifstream ifs("input.txt");

    // 1번
    // Exchange Sort, Quick Sort 비교, 오름차순 정렬
    for (int i = 0; i < 3; i++) {
        ifs >> n;
        in[i] = n;

        unsigned long long * ev = new unsigned long long[n];
        unsigned long long * qv = new unsigned long long[n];
        for (int j = 0; j < n; j++) {
            ev[j] = qv[j] = j;
        }
        // Exchange Sort
        init(); // key_compare 초기화
        clock_t t = clock();
        exchange_sort(ev, n);
        t = clock() - t; // 시간 저장
        unsigned long long es_key = key_compare;
        double es_time = (double)(t) / CLOCKS_PER_SEC;
        // Quick Sort
        init(); // key compare 초기화
        t = clock();
        quick_sort(qv, 0, n - 1);
        t = clock() - t; // 시간 저장
        unsigned long long qs_key = key_compare;
        double qs_time = (double)(t) / CLOCKS_PER_SEC;

        result[0][i] = es_key;
        result[1][i] = qs_key;
        ti[0][i] = es_time;
        ti[1][i] = qs_time;

        delete ev, qv;
    }

    // 2번
    // Merge Sort, Quick Sort 비교, 랜덤
    srand((unsigned int)time(0));
    for (int i = 0; i < 3; i++) {
        ifs >> n;
        in2[i] = n; // case N 저장

        unsigned long long * mv = new unsigned long long[n+1];
        unsigned long long * qv = new unsigned long long[n+1];

        unsigned long long kc_ms = 0;     // key compares of merge
        unsigned long long kc_qs = 0;     // key compares of quick
        double et_ms = 0;  // ex.time of merge
        double et_qs = 0;  // ex.time of quick

        // Random Number
        for (int k = 0; k < 5; k++) {
            for (int j = 0; j < n; j++) {
                unsigned long long push_num = (unsigned long long)rand() % RAND_MAX;
                mv[j] = qv[j] = push_num;
            }

            // mergesort
            init();  // key_compare 초기화
            clock_t t = clock();
            mergesort(mv, 0, n - 1);  // 실행
            t = clock() - t;
            kc_ms += key_compare;
            et_ms += (double)(t) / CLOCKS_PER_SEC;  // 경과 시간 저장

            // quicksort
            init();  // key_compare 초기화
            t = clock();
            quick_sort(qv, 0, n - 1);  // 실행
            t = clock() - t;
            kc_qs = key_compare;
            et_qs = (double)(t) / CLOCKS_PER_SEC;  // 경과 시간 저장


        }

        kc_ms /= 5;
        kc_qs /= 5;
        et_ms /= 5.0;
        et_qs /= 5.0;

        result2[0][i] = kc_ms;
        result2[1][i] = kc_qs;
        ti2[0][i] = et_ms;
        ti2[1][i] = et_qs;

        delete mv, qv;
    }
    //                                    N = Case1    N = Case 2    N = Case 3
    printf("%-14s\t %14s\t N=%-10d\t N=%-10d\t N=%-10d\n", sp, sp, in[0], in[1], in[2]);
    // Exchange Sort    Key Compares
    //                    Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", ex, kc, result[0][0], result[0][1], result[0][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti[0][0], ti[0][1], ti[0][2]);
    // Quick Sort    Key Compares
    //                Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", qu, kc, result[1][0], result[1][1], result[1][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti[1][0], ti[1][1], ti[1][2]);
    printf("\n\n");

    //                                    N = Case1    N = Case 2    N = Case 3
    printf("%-14s\t %14s\t N=%-10d\t N=%-10d\t N=%-10d\n", sp, sp, in2[0], in2[1], in2[2]);
    // Merge Sort    Key Compares
    //                    Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", me, kc, result2[0][0], result2[0][1], result2[0][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti2[0][0], ti2[0][1], ti2[0][2]);
    // Quick Sort    Key Compares
    //                Exe.Time
    printf("%-14s\t %-14s\t %-12llu\t %-12llu\t %-12llu\t\t\n", qu, kc, result2[1][0],    result2[1][1], result2[1][2]);
    printf("%-14s\t %-14s\t %-12lf\t %-12lf\t %-12lf\t\t\n", sp, et, ti2[1][0],    ti2[1][1], ti2[1][2]);
}

void exchange_sort(unsigned long long * v, int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            key_compare++;
            if (v[i] > v[j]) {
                unsigned long long temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }
}

void merge(unsigned long long * v, int low, int mid, int high) {
    int i, j, k;
    i = low;      // 왼쪽 시작
    j = mid + 1;  // 오른쪽 시작
    k = low;      // 결과 배열 인덱스
    unsigned long long *temp = new unsigned long long[high + 1];
    while (i <= mid && j <= high) {
        if (v[i] < v[j]) {
            key_compare++;
            temp[k] = v[i];
            i++;
        }
        else {
            key_compare++;
            temp[k] = v[j];
            j++;
        }
        k++;
    }
    while (i <= mid) {
        key_compare++;
        temp[k] = v[i];
        i++;
        k++;
    }

    while (j <= high) {
        key_compare++;
        temp[k] = v[j];
        j++;
        k++;
    }
    for (int i = low; i <= high; i++) {
        v[i] = temp[i];
    }
    delete temp;
}
void mergesort(unsigned long long * v, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        mergesort(v, low, mid);
        mergesort(v, mid + 1, high);
        merge(v, low, mid, high);
    }
}

void quick_sort(unsigned long long * v, int left, int right) {
    int i = left, j = right;
    unsigned long long pivot = v[left];
    do {
        while (v[i] < pivot) {
            key_compare++;
            i++;
        }
        while (v[j] > pivot) {
            key_compare++;
            j--;
        }
        if (i <= j) {
            if (v[i] > v[j]) {
                unsigned long long temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
            i++;
            j--;
        }
    } while (i <= j);
    if (left < j) {
        quick_sort(v, left, j);
    }
    if (i < right) {
        quick_sort(v, i, right);
    }
}