fork download
copy 
  1. #include <iostream>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. int srav=0,pris=0;
  6.  
  7. void merge(int a[], int l, int mind, int r) {
  8.     int i, j, k;
  9.     int n1=mind-l+1;
  10.     int n2=r-mind;
  11.     int L[n1], R[n2];
  12.     for (i=0;i<n1;i++) {
  13.         L[i]=a[l+i];
  14.         ++pris;
  15.     }
  16.     for (j=0;j<n2;j++) {
  17.         R[j]=a[mind+1+j];
  18.         ++pris;
  19.     }
  20.     i=0;
  21.     j=0;
  22.     k=l;
  23.     while (i<n1&&j<n2) {
  24.         ++srav;
  25.         if (L[i]<=R[j]) {
  26.             a[k]=L[i];
  27.             ++pris;
  28.             ++i;
  29.         }
  30.         else {
  31.             a[k]=R[j];
  32.             ++pris;
  33.             ++j;
  34.         }
  35.         ++k;
  36.     }
  37.     while (i<n1) {
  38.         a[k]=L[i];
  39.         ++srav;
  40.         i++;
  41.         k++;
  42.     }
  43.     while (j<n2) {
  44.         a[k]=R[j];
  45.         ++pris;
  46.         j++;
  47.         k++;
  48.     }
  49.     return;
  50. }
  51.  
  52. void merge_sort(int a[], int l, int r) {
  53.     if (l<r) {
  54.     int mid=l+(r-l)/2;
  55.     merge_sort(a,l,mid);
  56.     merge_sort(a,mid+1,r);
  57.     merge(a,l,mid,r);
  58. }
  59. return;
  60. }
  61.  
  62. int main() {
  63. 	int n,f=0,sumpris=0,sumsrav=0,i=0;
  64. 	cin>>n;
  65. 	srand(time(NULL));
  66. 	int a[n];
  67. 	for (f=0;f<7;++f) {
  68. 	i=0;
  69. 	srav=0;
  70. 	pris=0;
  71. 	while (i<n) {
  72. 		a[i]=rand()%150;
  73. 		++i;
  74. 	}
  75. 	merge_sort(a,0,n-1);
  76. 	sumsrav+=srav;
  77. 	sumpris+=pris;
  78.     cout<<"сравнений="<<srav<<" "<<"присваиваний="<<pris<<endl;
  79. 	}
  80. 	cout<<"среднее сравнений="<<sumsrav/7<<" "<<"среднее присваиваний="<<sumpris/7;
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
4000
stdout
copy 
сравнений=45321 присваиваний=93315
сравнений=45387 присваиваний=93297
сравнений=45387 присваиваний=93217
сравнений=45319 присваиваний=93295
сравнений=45358 присваиваний=93227
сравнений=45346 присваиваний=93240
сравнений=45353 присваиваний=93265
среднее сравнений=45353 среднее присваиваний=93265
https://ideone.com/TJfYTU
language:
C++ (gcc 8.3)
created:
3 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!