Visual Studio 2017 (C++) 자연 합병 정렬

C++

#include<iostream>

#include<time.h>

#include "sort.h"

using namespace std;

const int N = 100000;

void MergeSort(int arr[], int l, int r, int divide)

{

int *first_Arr = new int[N + 1];

//int first_Arr[N + 1];

int first_Cnt = 0;

int *second_Arr = new int[N + 1];

//int second_Arr[N + 1];

int second_Cnt = 0;

for (int i = l; i <= divide; i++)

first_Arr[++first_Cnt] = arr[i];

for (int i = divide + 1; i <= r; i++)

second_Arr[++second_Cnt] = arr[i];

int first_index = 1;

int second_index = 1;

int present_Position = 0;

for (int i = l; i < l + (first_Cnt + second_Cnt); i++)

{

arr[i] = first_Arr[first_index] > second_Arr[second_index] ? second_Arr[second_index++] : first_Arr[first_index++];

if (first_index == first_Cnt + 1) // 첫번째 배열이 다 들어가서 두번째 배열만 넣어주면 되는 경우

{

for (int j = i + 1; j < l + (first_Cnt + second_Cnt); j++)

arr[j] = second_Arr[second_index++];

break;

}

else if (second_index == second_Cnt + 1) // 두번째 배열이 다 들어가서 첫번째 배열만 넣어주면 되는 경우

{

for (int j = i + 1; j < l + (first_Cnt + second_Cnt); j++)

arr[j] = first_Arr[first_index++];

break;

}

}

delete[] first_Arr;

delete[] second_Arr;

first_Arr = NULL;

second_Arr = NULL;

}

void NaturalMergeSort(int arr[], int l, int r)

{

int check_Cnt = 0; // 2개 일때 합병

int first_Merge_start = 1;

int check_Point;

int sw = 0;

for (int i = l + 1; i <= r; i++)

{

if (arr[i - 1] > arr[i])

{

check_Cnt++;

sw = 1;

if (check_Cnt == 1)

check_Point = i - 1;

}

if (check_Cnt == 2)

{

MergeSort(arr, first_Merge_start, i - 1, check_Point);

check_Cnt = 0;

first_Merge_start = i;

}

if (i == r && check_Cnt == 1)

MergeSort(arr, first_Merge_start, i, check_Point);

}

if (sw == 1)

NaturalMergeSort(arr, 1, N);

}

int main()

{

srand(time(NULL));

int *arr = new int[N + 1];

double start_time;

int rever = N;

for (int i = 1; i <= N; i++)

arr[i] = rever--;

start_time = clock();

NaturalMergeSort(arr, 1, N);

cout << "총 걸린 시간 = " << (clock() - start_time)/CLOCKS_PER_SEC << "초" << endl;

//for (int i = 1; i <= N; i++)

// cout << arr[i] << " ";

CheckSort(arr, N);

delete[] arr;

arr = NULL;

return 0;

}

ADL

Natural_Merge_Sort(arr[], l, r)

     Arr_Cnt ← 1;

     run[Arr_Cnt][0] ← 1;

     for(i = l; i < r; i++) do {

         if(arr[i] > arr[i+1]) then {

             run[Arr_Cnt][1] = i;

             Arr_Cnt ← Arr_Cnt + 1;

             run[Arr_Cnt][0] = i + 1;

             }

     run[Arr_Cnt][1] = r;

     while(Arr_Cnt > 1) do {

         check ← 1;

             for (i = 1; i <= Arr_Cnt – 1; i ← i + 2) do {

                 MergeSort(Arr,run[i][0], run[i+1][1], run[i][1]);

                 run[check][0] = run[i][0];

                 run[check][1] = run[i + 1][1];

                 check++;

                 }

             run[check][0] = run[Arr_Cnt][0];

             run[check][0] = run[Arr_Cnt][1];

             Arr_Cnt ← Arr_Cnt - (check – 1 );

             }

end Natural_Merge_Sort(arr[], l, r, divide)

MergeSort(arr[], l, r, divide)

     for(i = divide + 1; i > l; i ← i – 1) do {

         merge_Arr[i-1] = arr[i-1];

         }

     for(j = divide;j < r; j ← j + 1) do {

         merge_Arr[r + divide – j] = arr[j + 1];

end MergeSort(arr[], l, r, divide)