구현 - 버블정렬, 선택 정렬, 삽입 정렬, 셸 정렬

이제 문제는 n log n 정렬들이군..

#include <iostream>
#include <ctime>
using namespace std;
 
 
constexpr int arrSize =40000;
 
void bubble(int* arr, int size)
{
    cout << "Bubble Sort " << endl;
    for (int i = size - 1; i >= 0; --i)
        for (int j = 0; j < i; ++j)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}
 
void selection(int* arr, int size)
{
    cout << "Selection Sort " << endl;
    for (int i = 0; i < size - 1; ++i)
    {
        int leastIdx = i;
        for (int j = i + 1; j < size; ++j)
            if (arr[j] < arr[leastIdx])
                leastIdx = j;
 
        swap(arr[i], arr[leastIdx]);
    }
}
 
void insertion(int* arr, int size)
{
    cout << "Insertion Sort " << endl;
 
    for (int i = 1; i < size; ++i)
    {
        int saved = arr[i];
        int j = i - 1;
        for ( ; j >= 0 && saved < arr[j]; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = saved;
    }
}
 
void shell(int* arr, int size)
{
    cout << "Shell Sort" << endl;
 
    for (int gap = size / 2; gap >0; gap /= 2)
    {
        if (gap % 2 == 0) ++gap;
        for (int i = gap; i < size; i += gap)
        {
            int j = i - gap;
            int saved = arr[i];
            for ( ; j >= 0 && saved < arr[j]; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = saved;
        }
    }
}
 
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(bubble);
 
    testSort(selection);
 
    testSort(insertion);
 
    testSort(shell);
 
    return 0;
}