자료구조 6번째 과제

main.cpp

#include <iostream>
#include <sys/time.h>
#include "sort.hpp"
#include "test-gen.hpp"

int main(int argc, char **argv) {
    srand(time(NULL));
    const int iteration = 1;
    const int n = 500000;
    int **arr = new int* [iteration];

    struct timeval endtime;
    struct timeval begtime;

    for (int i=0; i<iteration; ++i) {
        arr[i] = new int[n];
        QuickGenCase(arr[i], n);
    }

    for (int i=0; i<n; ++i) {
        cout << arr[0][i] << " ";
    }

    return 0;

    gettimeofday(&begtime, NULL);
    for (int i=0; i<iteration; ++i)
        QuickSort(arr[i], 0, n-1);

    gettimeofday(&endtime, NULL);

    long endtimeu = (endtime.tv_sec*1000000) + endtime.tv_usec;
    long begtimeu = (begtime.tv_sec*1000000) + begtime.tv_usec;

    cout << endtimeu - begtimeu << endl;

    // Insertion
    //  50 .000002957
    // 500 .000394173
    //1000 .001512885
    //2000 .005792753
    //3000 .013050949
    //4000 .023877072
    //5000 .03721402
    //500000 370.685248

    // Quick Worst
    //  50 1421
    // 500 126746
    //1000 503496
    //2000 2006996
    //3000 4510496
    //4000 8013996
    //5000 12517496
    //500000

    //10000 50034996

    return 0;
}

sort.hpp

#pragma once
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

template<typename T>
void Insert(const T& e, T *a, int i) {
    while (e < a[i] && i >= 0) {
        a[i+1] = a[i];
        i--;
    }
    a[i+1] = e;
}

template<typename T>
void InsertionSort(T *a, const int size) {
    for (int j = 1; j < size; ++j) {
        T temp = a[j];
        Insert(temp, a, j-1);
    }
}

template<typename T>
inline int MedianOfThree(T *a, int left, int right) {
    int mid = (right+left)/2;

    if (a[left] > a[right]) std::swap(a[left], a[right]);
    if (a[right] > a[mid]) std::swap(a[left], a[mid]);
    if (a[left] > a[mid]) std::swap(a[right], a[mid]);

    return a[left];
}

long globalComp = 0;

template<typename T>
void LPQuickSort(T *a, const int left, const int right) {
    if (left < right) {
        int i = left;
        int j = right + 1;
        int pivotIndex = left;

        // if (left != pivotIndex) std::swap(a[left], a[pivotIndex]), ++globalComp;
        int pivot = a[left];

        do {
            do i++, ++globalComp; while (a[i] < pivot);
            do j--, ++globalComp; while (a[j] > pivot);
            if (i < j) std::swap(a[i], a[j]), ++globalComp;
            ++globalComp;
        } while(i < j);
        std::swap(a[left], a[j]);
        ++globalComp;

        LPQuickSort(a, left, j-1);
        LPQuickSort(a, j+1, right);
    }
}

template<typename T>
void QuickSort(T *a, const int left, const int right) {
    if (left < right) {
        int i = left;
        int j = right+1;

        int pivot = MedianOfThree(a, left, right);
        do {
            do ++i, ++globalComp; while (a[i] < pivot);
            do --j, ++globalComp; while (a[j] > pivot);
            if (i < j) std::swap(a[i], a[j]), ++globalComp;
            ++globalComp;
        } while(i < j);
        std::swap(a[left], a[j]), ++globalComp;

        QuickSort(a, left, j-1);
        QuickSort(a, j+1, right);
    }
}

template<typename T>
void Merge(T *initList, T *mergedList, const int l, const int m, const int n) {
    int i1=l, iResult=l, i2=m+1;
    for (; i1<=m && i2<=n; iResult++) {
        if (initList[i1] <= initList[i2]) {
            mergedList[iResult] = initList[i1];
            i1++;
        } else {
            mergedList[iResult] = initList[i2];
            i2++;
        }
    }

    std::copy(initList+i1, initList+m+1, mergedList+iResult);
    std::copy(initList+i2, initList+n+1, mergedList+iResult);
}

template<typename T>
void MergePass(T *initList, T *resultList, const int n, const int s) {
    int i=0;
    for (; i<=n-2*s+1; i+=2*s) {
        Merge(initList, resultList, i, i+s-1, i+2*s-1);
    }

    if ((i+s-1)<n) Merge(initList, resultList, i, i+s-1, n);
    else std::copy(initList+i, initList+n+1, resultList+i);
}

template<typename T>
void MergeSort(T *a, const int n) {
    T *tempList = new T[n+1];
    for (int l=1; l<n; l*=2) {
        MergePass(a, tempList, n, l);
        l *= 2;
        MergePass(tempList, a, n, l);
    }

    delete [] tempList;
}

test-gen.hpp

#pragma once
#include "sort.hpp"
#include <algorithm>
#include <cstdlib>

void ConstantsGenCase(int *a, const int n) {
    for (int i=0; i<n; ++i) a[i] = 1;
}

void IncreGenCase(int *a, const int n) {
	for (int i=0; i<n; ++i) a[i] = i;
}

void InsertionGenCase(int *a, const int n) {
    for (int i=0, c=n; i<n; ++i, --c) {
        a[i] = c;
    }
}

template <typename T>
void Permute(T *a, int n) {
    for (int i=n-1; i>=2; i--) {
        int j=rand()%i;
        std::swap(a[j], a[i]);
    }
}

int QuickGenCase(int *a, const int n) {
    int *temp = new int[n];
    int *temp2 = new int[n];
    const int iterations = 1;
    for (int i=0; i<n; ++i) {
        temp[i] = i;
    }

    int max = 0;
    for (int i=0; i<iterations; ++i) {
        globalComp = 0;
        Permute(temp, n);
        copy(temp, temp+n, temp2);

        QuickSort(temp, 0, n-1);

        if (max < globalComp) {
            max = globalComp;
            cerr <<globalComp <<endl;
            copy(temp, temp+n, a);
        }
    }
//10000016
//10559234
//16798052

    delete []temp;
    return max;
}

void MergeGenCase(int *a, const int n) {
    InsertionGenCase(a, n);
}