알고리즘 Part 2

#include <cstdio>
#include <cstdlib>
#include <random>
#include <chrono>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
template <typename Type>
void Insertion_Sort(Type *_array, int _n)
{
    // 0th index가 정렬되었다고 가정
    for (int i = 1; i < _n; i++)
    {
        // 1th index부터 탐색
        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 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;
            }
        }
        //오른쪽으로 다 밀고 맨 왼쪽 값이 key 값보다 크다면!
        if (_array[0] > temp)
        {
            _array[0] = temp;
        }
    }
}
 
template <typename Type>
bool Is_Sorted(Type *_array, int _n)
{
    //정렬이 잘 되었는지 check
    for (int i = 1; i < _n; i++)
    {
        if (_array[i - 1] > _array[i])
        {
            return false;
        }
    }
    return true;
}
 
int main(int argc, char **argv)
{
    // Get random number
    random_device rd;
    default_random_engine gen(rd());
    uniform_int_distribution<int> dist(0, 10 * 1000 * 1000);
 
    int n = atoi(argv[1]);
 
    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]);
    }
 
    // Set start time
    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)
    {
        // STL function
        // 시작, 끝 주소 인자
        sort(&(data[0]), &(data[n]));
    }
    else
    {
        // do something
    }
 
    printf("Sorted : \n");
 
    //for (int i = 0; i < n; i++) {
    //   printf("10%d\n", data[i]);
    //}
 
    // Set end time
    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;
}