fork(1) download
copy 
  1. #include <iostream>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. int pris=0,srav=0;
  6.  
  7. void qsort(int a[], int n) {
  8.     int i=0;
  9.     int j=n-1;
  10.     int mid=a[n/2];
  11.     ++pris;
  12.     while (i<=j) {
  13.         ++srav;
  14.         while(a[i]<mid) {
  15.             i++;
  16.             ++srav;
  17.         }
  18.         ++srav;
  19.         while(a[j]>mid) {
  20.             j--;
  21.             ++srav;
  22.         }
  23.         if (i<=j) {
  24.             int t=a[i];
  25.             a[i]=a[j];
  26.             a[j]=t;
  27.             pris+=3;
  28.             i++;
  29.             j--;
  30.         }
  31.     }
  32.     if(j>0) {
  33.         qsort(a,j+1);
  34.     }
  35.     if (i<n) {
  36.         qsort(a,n-i);
  37.     }
  38. }
  39.  
  40. int main() {
  41. 	int n,f=0,sumpris=0,sumsrav=0,i=0;
  42. 	cin>>n;
  43. 	srand(time(NULL));
  44. 	int a[n];
  45. 	for (f=0;f<7;++f) {
  46. 	i=0;
  47. 	srav=0;
  48. 	pris=0;
  49. 	while (i<n) {
  50. 		a[i]=rand()%150;
  51. 		++i;
  52. 	}
  53. 	qsort(a,n);
  54. 	sumsrav+=srav;
  55. 	sumpris+=pris;
  56.     cout<<"сравнений="<<srav<<" "<<"присваиваний="<<pris<<endl;
  57. 	}
  58. 	cout<<"среднее сравнений="<<sumsrav/7<<" "<<"среднее присваиваний="<<sumpris/7;
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
60
stdout
copy 
сравнений=467 присваиваний=321
сравнений=402 присваиваний=312
сравнений=456 присваиваний=322
сравнений=451 присваиваний=279
сравнений=549 присваиваний=315
сравнений=368 присваиваний=271
сравнений=410 присваиваний=344
среднее сравнений=443 среднее присваиваний=309
https://ideone.com/K4RFyA
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!