fork download
copy 
  1. #include<iostream>
  2. #include <ctime>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. using namespace std;
  6. int turns = 0, mergetime, quicktime;
  7. int data_num;
  8. int* data_array;
  9. int* arr2;
  10. int timecheck[2][6];
  11.  
  12. void mergesort(int low, int high, int*);
  13. void merge(int*,int, int);
  14. void quick(int, int, int*);
  15.  
  16. int main() {
  17. 	int i, j;
  18. 	while(turns < 1){
  19. 		cin >> data_num;
  20. 		data_array = new int[data_num];
  21. 		arr2 = new int[data_num];
  22. 		if(turns < 3) {
  23. 			for(i = 0; i < data_num; i++)
  24. 				data_array[i] = rand()% data_num;
  25. 			sort(data_array, data_array+data_num);
  26. 		}
  27. 		else {
  28. 			for(i = 0; i < data_num; i++)
  29. 				data_array[i] = rand()% data_num;
  30. 		}
  31. 		clock_t start = clock();
  32. 		mergesort(0, data_num-1, data_array);
  33. 		clock_t end = clock();
  34. 		timecheck[0][turns] = (double)(end - start)/CLOCKS_PER_SEC;
  35. 		cout << "mergeSorting: " << timecheck[0][0] << "  ";
  36. 		start = clock();
  37. 		quick(0, data_num-1, data_array);
  38. 		end = clock();
  39. 		timecheck[1][turns] = (double)(end - start)/CLOCKS_PER_SEC;
  40. 		turns++;
  41. 	}
  42.  
  43. 	cout << "mergeSorting: " << timecheck[0][0] << "  ";
  44. 	return 0;
  45. }
  46.  
  47. void mergesort(int low, int high, int*array) {
  48.     int mid = (low + high) / 2;
  49.     if (low < high) {
  50.         mergesort(low, mid, array);
  51.         mergesort(mid+1, high, array);
  52.         merge(array, low, high);
  53.     }
  54. }
  55.  
  56. void merge(int *arr, int low, int high) {
  57.     int mid = (low + high) / 2;
  58.     int i = low;
  59.     int k = low;
  60.     int j = mid+1;
  61.     while (i <= mid && j <= high) {
  62.         if (arr[i] < arr[j]) // 작은순으로 정렬되어잇을것이므로, 나뉜 각 배열의 첫원소끼리 먼저 비교
  63.             arr2[k++] = arr[i++];
  64.         else arr2[k++] = arr[j++];
  65.     }
  66.  
  67.     if (i > mid) {
  68.         while (j <= high)
  69.             arr2[k++] = arr[j++];
  70.     }
  71.     else {
  72.         while (i <= mid)
  73.             arr2[k++] = arr[i++];
  74.     }
  75.  
  76.     for (i = low; i <= high; i++) {
  77.         arr[i] = arr2[i];
  78.     }
  79. }
  80.  
  81. void swap(int* a, int* b) {
  82.    int temp = *a;
  83.    *a = *b;
  84.    *b = temp;
  85. }
  86.  
  87. void quick(int low, int high, int* arr) {
  88.    int pivot = low;
  89.    int i = low + 1;
  90.    int j = pivot;
  91.    if (low < high) {
  92.       while (i <= high) {
  93.          if (arr[i] < arr[pivot]) {
  94.             j++;
  95.             swap(arr[i], arr[j]);
  96.          }
  97.          i++;
  98.       }
  99.       swap(arr[j], arr[low]);
  100.       pivot = j;
  101.       quick(low, pivot - 1, arr);
  102.       quick(pivot + 1, high, arr);
  103.    }
  104. }
Success #stdin #stdout 0.11s 4564KB
comments (?)
stdin
copy 
20000
stdout
copy 
mergeSorting: 0  mergeSorting: 0
https://ideone.com/dFe2ES
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!