[알고리즘] ep1-6+) 퀵정렬의 다양한 버전

(출력형식)

Limit         결정적1           결정적3              무작위1           무작위3
1        X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX

100    X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX

500   X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX

1000  X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX

(참고: X.XXXXXXXX는 측정된 cputime in milliseconds).

 

 

[주요 함수들의 설계 가이드라인]
global integer n = 100000
global array Limits = {1, 100, 500, 1000}

 

Alg main()

1. A ← createArray()
2. for each Limit in Limits {quick-sort limit sizes}
    for each mode in ('deterministic1', 'deterministic3', 'randomized1', 'randomized3')
        A' ← A {copy array}
        quickSort(A', n)
        printCPUTime()
3. return

 

Alg createArray()

input: none
output: array A of size n

1. for i ← 0 to n – 1
    A[i] ← a random integer between 1 and n
2. return A

 

Alg quickSort(A, n)

input: array A, integer n, Limit {Limit is global}
output: sorted array A

1. rQuickSort(A, 0, n - 1)
2. if (Limit > 1)
    insertionSort(A, n)
3. return

 

Alg rQuickSort(A, l, r)

input: array A, index l, r, integer Limit {Limit is global}
output: completely or partially sorted array A

1. if (r - l ≥ Limit)
    k ← findPivot(A, l, r)
    a, b ← inPlacePartition(A, l, r, k)
    rQuickSort(A, l, a - 1)
    rQuickSort(A, b + 1, r)

 

Alg findPivot(A, l, r)

1. if (mode = 'deterministic1')
    return r
2. if (mode = 'randomized1')
    return a random integer between l and r
3. if (r - l = 1)
    return l
4. switch (mode) {select three positions}
    'deterministic3': a, b, c ← l, (l + r)/2, r
    'randomized3': a, b, c ← 3 random integers between l and r
5. return findIndexOfMedianOfThree(a, b, c) {index of median of A[a], A[b], A[c]}

 

주의: 위 inPlacePartition은 부리스트에 중복 키가 존재하더라도 분할을 수행하는 버전이어야 한다(심층문제 8-2 참고).

 

 

 

(전체코드) - Windows에서만 실행 가능

// 퀵정렬의 다양한 버전 비교실험
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#pragma warning(disable:4996)

int g_n = 100000;
int g_Limits[4] = {1, 100, 500, 1000};
char* g_modes[4] = {"deterministic1", "deterministic3", "randomized1", "randomized3"};
char* g_curMode;
int g_curLimit;

int* createArray();
void quickSort(int* A, int n);
void rQuickSort(int* A, int l, int r);
int findPivot(int* A, int l, int r);
void insertionSort(int* A, int l, int r);
void inPlacePartition(int* A, int l, int r, int* i, int* j);

int main() {
    srand(time(NULL)); // 랜덤 시드 설정
    LARGE_INTEGER ticksPerSec; // 초당 타이머 틱 수
    QueryPerformanceFrequency(&ticksPerSec); // 타이머의 빈도 설정
    LARGE_INTEGER start, end, diff;
    int* A = createArray(); // 원본 랜덤값 배열 생성
    int* A_copy = (int*)malloc(g_n * sizeof(int));
    double results[4][4]; // 실행 시간 결과 저장 배열 (g_Limits x g_modes)

    for (int i = 0; i < 4; i++) { // 각 Limits에 대해 반복
        g_curLimit = g_Limits[i];
        for (int j = 0; j < 4; j++) { // 각 modes에 대해 반복
            g_curMode = g_modes[j];

            memcpy(A_copy, A, g_n * sizeof(int)); // memcpy를 사용하여 정수 배열을 복사

            QueryPerformanceCounter(&start);
            quickSort(A_copy, g_n);
            QueryPerformanceCounter(&end);
            diff.QuadPart = end.QuadPart - start.QuadPart;
            results[i][j] = ((double)diff.QuadPart / ((double)ticksPerSec.QuadPart * 1000)); // ms 단위로 변환하여 저장
        }
    }

    printf("Limit 결정적1 결정적3 무작위1 무작위3\n");
    for (int i = 0; i < 4; i++) {
        printf("%d ", g_Limits[i]);
        for (int j = 0; j < 4; j++) {
            printf("%.9lf ", results[i][j]); // 실행 시간 출력
        }
        printf("\n");
    }

    free(A);
    free(A_copy);
    return 0;
}

// 랜덤값 배열 생성
int* createArray() {
    int* A = (int*)malloc(g_n * sizeof(int));
    for (int i = 0; i < g_n; i++) {
        A[i] = rand() % g_n + 1;
    }
    return A;
}

void insertionSort(int* A, int l, int r) {
    int key, j;
    for (int i = l + 1; i <= r; i++) {
        key = A[i];
        j = i - 1;
        // 오른쪽으로 한 칸씩 땡긴다
        while (j >= l && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        // 삽입할 공간에 key값을 넣는다
        A[j + 1] = key;
    }
}

void quickSort(int* A, int n) {
    rQuickSort(A, 0, n - 1);
    if (g_curLimit > 1) { // 필요 시 삽입 정렬 호출
        insertionSort(A, 0, n - 1); 
    }
}

void rQuickSort(int* A, int l, int r) {
    if (r - l >= g_curLimit) { // 분할 기준 확인
        int i, j;
        int pivot = findPivot(A, l, r); // 피벗 찾기
        inPlacePartition(A, l, r, &i, &j); // 배열 분할
        rQuickSort(A, l, j); // 왼쪽 부분 배열 정렬
        rQuickSort(A, i, r); // 오른쪽 부분 배열 정렬
    } 
    else {
        insertionSort(A, l, r); // 작은 부분 배열은 삽입 정렬 수행
    }
}

int findPivot(int* A, int l, int r) {
    if (strcmp(g_curMode, "deterministic1") == 0) {
        return r; // 결정적1 모드에서는 오른쪽 끝을 피벗으로 사용
    } 
    else if (strcmp(g_curMode, "randomized1") == 0) {
        return rand() % (r - l + 1) + l; // 무작위1 모드에서는 랜덤 인덱스를 피벗으로 사용
    } 
    else if (r - l == 1) {
        return l; // 두 요소만 있을 경우 왼쪽을 피벗으로 사용
    } 
    else {
        int leftIdx, midIdx, rightIdx;
        if (strcmp(g_curMode, "deterministic3") == 0) {
            leftIdx = l;
            midIdx = (l + r) / 2;
            rightIdx = r;
        } 
        else if (strcmp(g_curMode, "randomized3") == 0) {
            leftIdx = rand() % (r - l + 1) + l;
            midIdx = rand() % (r - l + 1) + l;
            rightIdx = rand() % (r - l + 1) + l;
        }
        // 세 위치의 값 중 중앙값의 인덱스를 반환
        if (A[leftIdx] < A[midIdx])
            if (A[midIdx] < A[rightIdx])
                return midIdx;
            else if (A[leftIdx] < A[rightIdx])
                return rightIdx;
            else
                return leftIdx;
        else
            if (A[leftIdx] < A[rightIdx])
                return leftIdx;
            else if (A[midIdx] < A[rightIdx])
                return rightIdx;
            else
                return midIdx;
    }
}

// 배열 분할 함수
void inPlacePartition(int* A, int l, int r, int* i, int* j) {
    int pivotValue = A[(l + r) / 2]; // 피벗 값 설정
    *i = l;
    *j = r;
    int temp;
    while (*i <= *j) {
        while (A[*i] < pivotValue) (*i)++; // 왼쪽에서 피벗보다 큰 값을 찾음
        while (A[*j] > pivotValue) (*j)--; // 오른쪽에서 피벗보다 작은 값을 찾음
        if (*i <= *j) {
            temp = A[*i]; // swap
            A[*i] = A[*j];
            A[*j] = temp;
            (*i)++;
            (*j)--;
        }
    }
}

 

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)