버블, 삽입, 퀵 비교

#include <iostream>
#include <algorithm>
#include <time.h>

void Shuffle(int* index, int nMax);
void quickSort(int* arr, int start, int end);
void InsertionSort(int DataSet[], int Length);
void BubbleSort(int DataSet[], int Length);

#define SIZE_S 10000
#define SIZE_B 50000

int main()
{
    clock_t start, end;

    int arr1[SIZE_S] = { 0, };
    int arr2[SIZE_B] = { 0, };
    
    for (int i = 0; i < SIZE_S; i++) {
        arr1[i] = i;
        //std::cout << arr1[i] << " ";
    }
    //system("pause");
    for (int i = 0; i < SIZE_B; i++) {
        arr2[i] = i;
        //std::cout << arr2[i] << " ";
    }
    
    Shuffle(arr1, sizeof(arr1) / sizeof(arr1[0]));
    Shuffle(arr2, sizeof(arr2) / sizeof(arr2[0]));

    // 내장 함수 정렬

    start = clock();
    std::sort(arr1, arr1 + SIZE_S);
    end = clock();
    std::cout << "\n\t\tstd::sort 정렬 수행 시간\n\n\t" << SIZE_S << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    std::sort(arr1, arr1 + SIZE_S);
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    start = clock();
    std::sort(arr2, arr2+SIZE_B);
    end = clock();
    std::cout << "\n\t" << SIZE_B << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    std::sort(arr2, arr2 + SIZE_B);
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    Shuffle(arr1, sizeof(arr1) / sizeof(arr1[0]));
    Shuffle(arr2, sizeof(arr2) / sizeof(arr2[0]));
    
    // 퀵 정렬

    start = clock();
    quickSort(arr1, 0, SIZE_S - 1);
    end = clock();
    std::cout << "\n\t\t퀵 정렬 수행 시간\n\n\t" << SIZE_S << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    quickSort(arr1, 0, SIZE_S - 1);
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    start = clock();
    quickSort(arr2, 0, SIZE_B - 1);
    end = clock();
    std::cout << "\n\t" << SIZE_B << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    quickSort(arr2, 0, SIZE_B - 1);
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";
    
    Shuffle(arr1, sizeof(arr1) / sizeof(arr1[0]));
    Shuffle(arr2, sizeof(arr2) / sizeof(arr2[0]));

    // 버블 정렬

    start = clock();
    BubbleSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
    end = clock();
    std::cout << "\n\t\t버블 정렬 수행 시간\n\n\t" << SIZE_S << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    BubbleSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    start = clock();
    BubbleSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
    end = clock();
    std::cout << "\n\t" << SIZE_B << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    BubbleSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    Shuffle(arr1, sizeof(arr1) / sizeof(arr1[0]));
    Shuffle(arr2, sizeof(arr2) / sizeof(arr2[0]));

    // 삽입 정렬

    start = clock();
    InsertionSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
    end = clock();
    std::cout << "\n\t\t삽입 정렬 수행 시간\n\n\t" << SIZE_S << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    InsertionSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    start = clock();
    InsertionSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
    end = clock();
    std::cout << "\n\t" << SIZE_B << "개\t= " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초";

    start = clock();
    InsertionSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
    end = clock();
    std::cout << "\n\t정렬된 경우 = " << (double)(end - start) << " ms\t" << (double)(end - start) * 0.001 << "초" << "\n\n";

    return 0;
}


void Shuffle(int* index, int nMax) {
    int i, n;

    int nTmp;

    srand(time(NULL));

    for (i = nMax - 1; i >= 0; i--) {

        n = rand() % nMax;
        nTmp = index[i];
        index[i] = index[n];
        index[n] = nTmp;

    }

}

void quickSort(int* arr, int start, int end) {
    if (start >= end) return;
    
    int key = start;
    int i = start + 1;
    int j = end;
    int temp;

    while (i <= j) {
        while (arr[key] >= arr[i]) i++;
        while (arr[key] <= arr[j] && key < j) j--;

        if (j < i) {
            temp = arr[j];
            arr[j] = arr[key];
            arr[key] = temp;
        }
        else {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }

    quickSort(arr, start, j - 1);
    quickSort(arr, j+1, end);
}

void InsertionSort(int DataSet[], int Length)
{
    int i = 0;
    int j = 0;
    int value = 0;

    for (i = 1; i < Length; i++)
    {
        if (DataSet[i - 1] <= DataSet[i])
            continue;

        value = DataSet[i];

        for (j = 0; j < i; j++)
        {
            if (DataSet[j] > value)
            {
                memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));
                DataSet[j] = value;
                break;
            }
        }
    }
}
void BubbleSort(int DataSet[], int Length)
{
    int i = 0;
    int j = 0;
    int temp = 0;

    for (i = 0; i < Length - 1; i++)
    {
        for (j = 0; j < Length - (i + 1); j++)
        {
            if (DataSet[j] > DataSet[j + 1])
            {
                temp = DataSet[j + 1];
                DataSet[j + 1] = DataSet[j];
                DataSet[j] = temp;
            }
        }
    }
}

실제로 시간 차이가 얼마나 나는지 확인해 보았다.