구현 - 병합 정렬, 퀵 정렬, 기수 정렬

#include <iostream>
#include <ctime>
using namespace std;
constexpr int arrSize = 200000;
 
void merge(int A[], int left, int mid, int right)
{
    static int sorted[arrSize];
 
    int i = left;        //left side
    int j = mid + 1;    //right side
    int k = left;        //sorted index
 
    while( i <= mid && j <= right)
        sorted[k++] = A[i] <= A[j] ? A[i++] : A[j++];
 
    if (i > mid)
        while (j <= right)
            sorted[k++] = A[j++];
    else
        while (i <= mid)
            sorted[k++] = A[i++];
 
    for (int i = left; i <= right; ++i)
        A[i] = sorted[i];
 
}
void mergeSort(int* a, int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(a, left, mid);
        mergeSort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}
 
void mergeSort(int* a, int size)
{
    cout << "merge sort" << endl;
    mergeSort(a, 0, size - 1);
}
 
 
int partition(int A[], int left, int right)
{
    int low = left;
    int high = right + 1;
    int pivot = A[left];
 
    swap(A[low], A[high]);
    while (low < high)
    {
        swap(A[low], A[high]);
        while (++low <= right && A[low] < pivot);
        while (--high >= left && A[high] > pivot);
    } 
 
    swap(A[left], A[high]);
    return high;
}
void quickSort(int A[], int left, int right)
{
    if (left < right)
    {
        int q = partition(A, left, right);
        quickSort(A, left, q - 1);
        quickSort(A, q + 1, right);
    }
}
void quickSort(int* a, int size)
{
    cout << "quick sort" << endl;
    quickSort(a, 0, size - 1);
}
 
 
#include <queue>
void radixSort(int* a, int size)
{
    cout << "radix sort" << endl;
    constexpr int ndigits = 2;
    constexpr int decimal = 10;
    queue<int> ques[10];
    int factor = 1;
    for(int d = 0; d < ndigits; ++d)
    {
        for (int i = 0; i < size; ++i)
            ques[(a[i] / factor) % decimal].push(a[i]);
        for (int b = 0, i = 0; b < decimal; ++b)
            while (!ques[b].empty())
            {
                a[i++] = ques[b].front();
                ques[b].pop();
            }
        factor *= 10;
    }
}
 
void testSort(void(*sortFunc)(int*, int))
{
    int arr[arrSize];
    cout << "size of n " << arrSize << endl;
    for (int i = 0; i < arrSize; ++i)
        arr[i] = rand() % 99;
 
    clock_t start, finish;
    double duration;
    start = clock();
 
    sortFunc(arr, arrSize);
 
    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "duration : " << duration << endl;
 
    if(arrSize < 100)
    for (int& a : arr)
        cout << a << " ";
    cout << endl << endl;
}
 
int main()
{
    srand(size_t(time(nullptr)));
 
    testSort(mergeSort);
 
    testSort(quickSort);
 
    testSort(radixSort);
 
    return 0;
}

밑과 같이 구현한 기수 정렬이 생각보다 느린데 왜 그런 것일까? 

1. 나눗셈?

2. deque기반 queue 문제?