fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <random>
  4. #include <algorithm>
  5. #include <chrono>
  6.  
  7. using namespace std;
  8.  
  9. // Генерация случайного массива
  10. void generateRandomArray(vector<double>& arr, int N)
  11. {
  12.     random_device rd;
  13.     mt19937 gen(rd());
  14.     uniform_real_distribution<> dis(-1000.0, 1000.0);
  15.  
  16.     arr.resize(N);
  17.  
  18.     for (int i = 0; i < N; i++)
  19.         arr[i] = dis(gen);
  20. }
  21.  
  22. // Генерация массива, отсортированного на 95%
  23. void generateAlmostSortedArray(vector<double>& arr, int N)
  24. {
  25.     generateRandomArray(arr, N);
  26.  
  27.     sort(arr.begin(), arr.end());
  28.  
  29.     int swaps = N * 0.05;
  30.  
  31.     random_device rd;
  32.     mt19937 gen(rd());
  33.     uniform_int_distribution<> dis(0, N - 1);
  34.  
  35.     for (int i = 0; i < swaps; i++)
  36.     {
  37.         int a = dis(gen);
  38.         int b = dis(gen);
  39.         swap(arr[a], arr[b]);
  40.     }
  41. }
  42.  
  43. // Сортировка вставками
  44. void insertionSort(vector<double>& arr)
  45. {
  46.     int n = arr.size();
  47.  
  48.     for (int i = 1; i < n; i++)
  49.     {
  50.         double key = arr[i];
  51.         int j = i - 1;
  52.  
  53.         while (j >= 0 && arr[j] > key)
  54.         {
  55.             arr[j + 1] = arr[j];
  56.             j--;
  57.         }
  58.  
  59.         arr[j + 1] = key;
  60.     }
  61. }
  62.  
  63. // Слияние для MergeSort
  64. void merge(vector<double>& arr, int left, int mid, int right)
  65. {
  66.     int n1 = mid - left + 1;
  67.     int n2 = right - mid;
  68.  
  69.     vector<double> L(n1), R(n2);
  70.  
  71.     for (int i = 0; i < n1; i++)
  72.         L[i] = arr[left + i];
  73.  
  74.     for (int j = 0; j < n2; j++)
  75.         R[j] = arr[mid + 1 + j];
  76.  
  77.     int i = 0, j = 0, k = left;
  78.  
  79.     while (i < n1 && j < n2)
  80.     {
  81.         if (L[i] <= R[j])
  82.             arr[k++] = L[i++];
  83.         else
  84.             arr[k++] = R[j++];
  85.     }
  86.  
  87.     while (i < n1)
  88.         arr[k++] = L[i++];
  89.  
  90.     while (j < n2)
  91.         arr[k++] = R[j++];
  92. }
  93.  
  94. // Сортировка слиянием
  95. void mergeSort(vector<double>& arr, int left, int right)
  96. {
  97.     if (left >= right)
  98.         return;
  99.  
  100.     int mid = (left + right) / 2;
  101.  
  102.     mergeSort(arr, left, mid);
  103.     mergeSort(arr, mid + 1, right);
  104.  
  105.     merge(arr, left, mid, right);
  106. }
  107.  
  108. // Измерение времени сортировки вставками
  109. double measureInsertion(vector<double> arr)
  110. {
  111.     auto start = chrono::high_resolution_clock::now();
  112.  
  113.     insertionSort(arr);
  114.  
  115.     auto end = chrono::high_resolution_clock::now();
  116.  
  117.     chrono::duration<double> diff = end - start;
  118.  
  119.     return diff.count();
  120. }
  121.  
  122. // Измерение времени сортировки слиянием
  123. double measureMerge(vector<double> arr)
  124. {
  125.     auto start = chrono::high_resolution_clock::now();
  126.  
  127.     mergeSort(arr, 0, arr.size() - 1);
  128.  
  129.     auto end = chrono::high_resolution_clock::now();
  130.  
  131.     chrono::duration<double> diff = end - start;
  132.  
  133.     return diff.count();
  134. }
  135.  
  136. int main()
  137. {
  138.     vector<int> sizes = {
  139.         1,2,4,8,16,32,64,128,256,512,
  140.         1024,2048,4096,8192,16384,32768,65536
  141.     };
  142.  
  143.     cout << "N\tInsertion Random\tInsertion 95%\tMerge Random\tMerge 95%\n";
  144.  
  145.     for (int N : sizes)
  146.     {
  147.         vector<double> arr1, arr2;
  148.  
  149.         // случайные массивы
  150.         generateRandomArray(arr1, N);
  151.         generateAlmostSortedArray(arr2, N);
  152.  
  153.         double t1 = measureInsertion(arr1);
  154.         double t2 = measureInsertion(arr2);
  155.  
  156.         generateRandomArray(arr1, N);
  157.         generateAlmostSortedArray(arr2, N);
  158.  
  159.         double t3 = measureMerge(arr1);
  160.         double t4 = measureMerge(arr2);
  161.  
  162.         cout << N << "\t"
  163.              << t1 << "\t"
  164.              << t2 << "\t"
  165.              << t3 << "\t"
  166.              << t4 << endl;
  167.     }
  168.  
  169.     return 0;}
Success #stdin #stdout 1.75s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N	Insertion Random	Insertion 95%	Merge Random	Merge 95%
1	2.39e-07	3.5e-08	5.7e-08	2.3e-08
2	9.1e-08	2.9e-08	5.59e-07	1.98e-07
4	1.4e-07	8.6e-08	5.07e-07	3.16e-07
8	1.73e-07	7.7e-08	8.21e-07	7.11e-07
16	3.44e-07	8.3e-08	1.946e-06	1.557e-06
32	6.8e-07	1.96e-07	3.521e-06	2.335e-06
64	1.4038e-05	8.02e-07	7.836e-06	6.009e-06
128	5.304e-06	1.404e-06	1.2959e-05	9.895e-06
256	2.2883e-05	3.247e-06	3.1947e-05	2.5153e-05
512	8.9145e-05	1.2677e-05	7.368e-05	5.3559e-05
1024	0.000361519	4.897e-05	0.000151969	0.000108394
2048	0.00140459	0.000206849	0.000350872	0.00022403
4096	0.00557089	0.000699296	0.000681444	0.00047095
8192	0.0224202	0.00279742	0.00133522	0.000970086
16384	0.0774303	0.0104451	0.00311466	0.00140022
32768	0.271252	0.0405842	0.00592066	0.00429861
65536	1.1339	0.116294	0.012313	0.00862695
https://ideone.com/lCb6uC
language:
C++ (gcc 8.3)
created:
12 hours 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!