#include<iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
int turns = 0, mergetime, quicktime;
int data_num;
int* data_array;
int* arr2;
int timecheck[2][6];
void mergesort(int low, int high, int*);
void merge(int*,int, int);
void quick(int, int, int*);
int main() {
int i, j;
while(turns < 1){
cin >> data_num;
data_array = new int[data_num];
arr2 = new int[data_num];
if(turns < 3) {
for(i = 0; i < data_num; i++)
data_array[i] = rand()% data_num;
sort(data_array, data_array+data_num);
}
else {
for(i = 0; i < data_num; i++)
data_array[i] = rand()% data_num;
}
clock_t start = clock();
mergesort(0, data_num-1, data_array);
clock_t end = clock();
timecheck[0][turns] = (double)(end - start)/CLOCKS_PER_SEC;
cout << "mergeSorting: " << timecheck[0][0] << " ";
start = clock();
quick(0, data_num-1, data_array);
end = clock();
timecheck[1][turns] = (double)(end - start)/CLOCKS_PER_SEC;
turns++;
}
cout << "mergeSorting: " << timecheck[0][0] << " ";
return 0;
}
void mergesort(int low, int high, int*array) {
int mid = (low + high) / 2;
if (low < high) {
mergesort(low, mid, array);
mergesort(mid+1, high, array);
merge(array, low, high);
}
}
void merge(int *arr, int low, int high) {
int mid = (low + high) / 2;
int i = low;
int k = low;
int j = mid+1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) // 작은순으로 정렬되어잇을것이므로, 나뉜 각 배열의 첫원소끼리 먼저 비교
arr2[k++] = arr[i++];
else arr2[k++] = arr[j++];
}
if (i > mid) {
while (j <= high)
arr2[k++] = arr[j++];
}
else {
while (i <= mid)
arr2[k++] = arr[i++];
}
for (i = low; i <= high; i++) {
arr[i] = arr2[i];
}
}
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void quick(int low, int high, int* arr) {
int pivot = low;
int i = low + 1;
int j = pivot;
if (low < high) {
while (i <= high) {
if (arr[i] < arr[pivot]) {
j++;
swap(arr[i], arr[j]);
}
i++;
}
swap(arr[j], arr[low]);
pivot = j;
quick(low, pivot - 1, arr);
quick(pivot + 1, high, arr);
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxhbGdvcml0aG0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCB0dXJucyA9IDAsIG1lcmdldGltZSwgcXVpY2t0aW1lOwppbnQgZGF0YV9udW07CmludCogZGF0YV9hcnJheTsKaW50KiBhcnIyOwppbnQgdGltZWNoZWNrWzJdWzZdOwoKdm9pZCBtZXJnZXNvcnQoaW50IGxvdywgaW50IGhpZ2gsIGludCopOwp2b2lkIG1lcmdlKGludCosaW50LCBpbnQpOwp2b2lkIHF1aWNrKGludCwgaW50LCBpbnQqKTsKCmludCBtYWluKCkgewoJaW50IGksIGo7Cgl3aGlsZSh0dXJucyA8IDEpewoJCWNpbiA+PiBkYXRhX251bTsKCQlkYXRhX2FycmF5ID0gbmV3IGludFtkYXRhX251bV07CgkJYXJyMiA9IG5ldyBpbnRbZGF0YV9udW1dOwoJCWlmKHR1cm5zIDwgMykgewoJCQlmb3IoaSA9IDA7IGkgPCBkYXRhX251bTsgaSsrKQoJCQkJZGF0YV9hcnJheVtpXSA9IHJhbmQoKSUgZGF0YV9udW07CgkJCXNvcnQoZGF0YV9hcnJheSwgZGF0YV9hcnJheStkYXRhX251bSk7CgkJfQoJCWVsc2UgewoJCQlmb3IoaSA9IDA7IGkgPCBkYXRhX251bTsgaSsrKQoJCQkJZGF0YV9hcnJheVtpXSA9IHJhbmQoKSUgZGF0YV9udW07CgkJfQoJCWNsb2NrX3Qgc3RhcnQgPSBjbG9jaygpOwoJCW1lcmdlc29ydCgwLCBkYXRhX251bS0xLCBkYXRhX2FycmF5KTsKCQljbG9ja190IGVuZCA9IGNsb2NrKCk7CgkJdGltZWNoZWNrWzBdW3R1cm5zXSA9IChkb3VibGUpKGVuZCAtIHN0YXJ0KS9DTE9DS1NfUEVSX1NFQzsKCQljb3V0IDw8ICJtZXJnZVNvcnRpbmc6ICIgPDwgdGltZWNoZWNrWzBdWzBdIDw8ICIgICI7CgkJc3RhcnQgPSBjbG9jaygpOwoJCXF1aWNrKDAsIGRhdGFfbnVtLTEsIGRhdGFfYXJyYXkpOwoJCWVuZCA9IGNsb2NrKCk7CgkJdGltZWNoZWNrWzFdW3R1cm5zXSA9IChkb3VibGUpKGVuZCAtIHN0YXJ0KS9DTE9DS1NfUEVSX1NFQzsKCQl0dXJucysrOwoJfQoJCgljb3V0IDw8ICJtZXJnZVNvcnRpbmc6ICIgPDwgdGltZWNoZWNrWzBdWzBdIDw8ICIgICI7CglyZXR1cm4gMDsKfQoKdm9pZCBtZXJnZXNvcnQoaW50IGxvdywgaW50IGhpZ2gsIGludCphcnJheSkgewogICAgaW50IG1pZCA9IChsb3cgKyBoaWdoKSAvIDI7CiAgICBpZiAobG93IDwgaGlnaCkgewogICAgICAgIG1lcmdlc29ydChsb3csIG1pZCwgYXJyYXkpOwogICAgICAgIG1lcmdlc29ydChtaWQrMSwgaGlnaCwgYXJyYXkpOwogICAgICAgIG1lcmdlKGFycmF5LCBsb3csIGhpZ2gpOwogICAgfQp9CiAKdm9pZCBtZXJnZShpbnQgKmFyciwgaW50IGxvdywgaW50IGhpZ2gpIHsKICAgIGludCBtaWQgPSAobG93ICsgaGlnaCkgLyAyOwogICAgaW50IGkgPSBsb3c7CiAgICBpbnQgayA9IGxvdzsKICAgIGludCBqID0gbWlkKzE7CiAgICB3aGlsZSAoaSA8PSBtaWQgJiYgaiA8PSBoaWdoKSB7CiAgICAgICAgaWYgKGFycltpXSA8IGFycltqXSkgLy8g7J6R7J2A7Iic7Jy866GcIOygleugrOuQmOyWtOyeh+ydhOqyg+ydtOuvgOuhnCwg64KY64mcIOqwgSDrsLDsl7TsnZgg7LKr7JuQ7IaM64G866asIOuovOyggCDruYTqtZAKICAgICAgICAgICAgYXJyMltrKytdID0gYXJyW2krK107CiAgICAgICAgZWxzZSBhcnIyW2srK10gPSBhcnJbaisrXTsKICAgIH0KIAogICAgaWYgKGkgPiBtaWQpIHsKICAgICAgICB3aGlsZSAoaiA8PSBoaWdoKQogICAgICAgICAgICBhcnIyW2srK10gPSBhcnJbaisrXTsKICAgIH0KICAgIGVsc2UgewogICAgICAgIHdoaWxlIChpIDw9IG1pZCkKICAgICAgICAgICAgYXJyMltrKytdID0gYXJyW2krK107CiAgICB9CiAKICAgIGZvciAoaSA9IGxvdzsgaSA8PSBoaWdoOyBpKyspIHsKICAgICAgICBhcnJbaV0gPSBhcnIyW2ldOwogICAgfQp9Cgp2b2lkIHN3YXAoaW50KiBhLCBpbnQqIGIpIHsKICAgaW50IHRlbXAgPSAqYTsKICAgKmEgPSAqYjsKICAgKmIgPSB0ZW1wOwp9Cgp2b2lkIHF1aWNrKGludCBsb3csIGludCBoaWdoLCBpbnQqIGFycikgewogICBpbnQgcGl2b3QgPSBsb3c7CiAgIGludCBpID0gbG93ICsgMTsKICAgaW50IGogPSBwaXZvdDsKICAgaWYgKGxvdyA8IGhpZ2gpIHsKICAgICAgd2hpbGUgKGkgPD0gaGlnaCkgewogICAgICAgICBpZiAoYXJyW2ldIDwgYXJyW3Bpdm90XSkgewogICAgICAgICAgICBqKys7CiAgICAgICAgICAgIHN3YXAoYXJyW2ldLCBhcnJbal0pOwogICAgICAgICB9CiAgICAgICAgIGkrKzsKICAgICAgfQogICAgICBzd2FwKGFycltqXSwgYXJyW2xvd10pOwogICAgICBwaXZvdCA9IGo7CiAgICAgIHF1aWNrKGxvdywgcGl2b3QgLSAxLCBhcnIpOwogICAgICBxdWljayhwaXZvdCArIDEsIGhpZ2gsIGFycik7CiAgIH0KfQ==