알고리즘 Part 3

#include <cstdio>
#include <cstdlib>
#include <random>
#include <chrono>
#include <algorithm>
#include <cstring>
 
// 배열의 크기가 6이하일때!
#define NUM_THRESHOLD 6
 
using namespace std;
 
 
template <typename Type>
void Insertion_Sort_without_Swap(Type* _array, int _n) {
    for (int i = 1; i < _n; i++) {
        Type temp = _array[i];
        for (int j = i; j > 0; j--) {
            if (_array[j - 1] > temp) {
                _array[j] = _array[j - 1];
            }
            else {
                _array[j] = temp;
                break;
            }
        }
        if (_array[0] > temp) {
            _array[0] = temp;
        }
    }
}
 
template <typename Type>
void Insertion_Sort(Type* _array, int _n) {
    for (int i = 1; i < _n; i++) {
        for (int j = i; j > 0; j--) {
            if (_array[j - 1] > _array[j]) {
                swap(_array[j - 1], _array[j]);
            }
            else {
                break;
            }
        }
    }
}
 
template <typename Type>
void Merge(Type *_arrayA, Type *_arrayB, int _nA, int _nB, Type *_arrayOut) {
    int posA = 0, posB = 0, k = 0;
    while (posA < _nA && posB < _nB) {
        if (_arrayA[posA] < _arrayB[posB]) {
            _arrayOut[k] = _arrayA[posA];
            posA++;
        }
        else {
            _arrayOut[k] = _arrayB[posB];
            posB++;
        }
        k++;
    }
    // 나머지
    for (; posA < _nA; posA++) {
        _arrayOut[k] = _arrayA[posA];
        k++;
    }
    // 나머지
    for (; posB< _nB; posB++) {
        _arrayOut[k] = _arrayB[posB];
        k++;
    }
}
 
template <typename Type>
void Merge_Sort(Type* _array, int _first, int _last) {
    // 배열의 크기 Check
    if (_last - _first <= NUM_THRESHOLD) {
        // 배열 시작 주소, 배열의 크기
        Insertion_Sort_without_Swap<Type>(&(_array[_first]), _last-_first);
    }
    else {
        int mid = (_first + _last) / 2;
        Merge_Sort<Type>(_array, _first, mid);
        Merge_Sort<Type>(_array, mid, _last);
        // additional Array to merge two sub-arrays
        Type* temp = new Type[_last - _first];
        Merge<Type>(&(_array[_first]),&(_array[mid]),mid-_first,_last-mid,temp);
        for (int i = 0; i < _last-_first; i++) {
            _array[_first + i] = temp[i];
        }
        delete[] temp;
    }
 
}
 
template <typename Type>
bool Is_Sorted(Type* _array, int _n) {
    for (int i = 1; i < _n; i++) {
        if (_array[i - 1] > _array[i]) {
            return false;
        }
    }
    return true;
}
 
int main(int argc, char**argv)
{
    random_device rd;
    default_random_engine gen(rd());
    uniform_int_distribution<int> dist(0, 10 * 1000 * 1000);
 
    int n = atoi(argv[1]);
    printf("n = %d\n", n);
    int* data = new int[n];
 
    printf("Data : \n");
    for (int i = 0; i < n; i++) {
        data[i] = dist(gen);
        //printf("10%d\n", data[i]);
    }
 
    chrono::time_point<chrono::system_clock> startTime = chrono::system_clock::now();
 
    if (strcmp(argv[2], "insertion") == 0) {
        Insertion_Sort<int>(data, n);
    }
    else if (strcmp(argv[2], "insertion_without_swap") == 0) {
        Insertion_Sort_without_Swap<int>(data, n);
    }
    else if (strcmp(argv[2], "std") == 0) {
        sort(&(data[0]), &(data[n]));
    }
    else if (strcmp(argv[2], "merge") == 0) {
        Merge_Sort(data,0,n);
    }
    else{}
 
    printf("Sorted : \n");
    
    //for (int i = 0; i < n; i++) {
    //   printf("10%d\n", data[i]);
    //}
 
    chrono::time_point<chrono::system_clock> endTime = chrono::system_clock::now();
    chrono::milliseconds timeDiff = chrono::duration_cast<chrono::milliseconds> (endTime - startTime);
    
    double T = timeDiff.count();
 
    printf("Runtime = %d ms\n", (int)T);
    bool flag = Is_Sorted<int>(data, n);
 
    if (flag) {
        printf("Correct\n");
    }
    else {
        printf("Wrong\n");
    }
 
    return 1;
}