SHARE
TWEET

sort123

ySiriuS17 Dec 15th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <time.h>
  3. #include <stdlib.h>
  4. using namespace std;
  5. int ksrav=0, kdo=0;
  6. void prost(int b[], int n){
  7.     int ksrav=0, kdo=0;                                                         for (int i=0; i<n; i++)cout<<b[i]<<' ';cout<<endl;
  8.     for (int i=1; i<n; i++){
  9.         int key=b[i];///значение
  10.         int j=i-1;   ///индекс
  11.         while (b[j]>key&&j>=0){ksrav++;
  12.             b[j+1]=b[j];       kdo++;
  13.             j--;
  14.         }
  15.         b[j+1]=key;            kdo++;                                           for (int i=0; i<n; i++)cout<<b[i]<<' ';cout<<endl;
  16.     }
  17.                                                                                 for (int i=0; i<n; i++)cout<<b[i]<<' ';
  18.  
  19.                                                                                 cout<<endl<<"Sravnenii : "<<ksrav<<endl<<"Deistvii : "<<kdo<<endl<<endl;
  20. }
  21. void binar(int b[], int n){
  22.                                                                                 for (int i=0; i<n; i++) cout<<b[i]<<' '; cout<<endl;
  23.     ksrav=0; kdo=0;
  24.     for (int i=1; i<n; i++){
  25.         if (b[i-1]>b[i]){
  26.             int key=b[i];
  27.             int left=0, right=i-1;
  28.             while (left<=right){            ksrav++;
  29.                 int sred=(left+right)/2;    kdo++;
  30.                 if (b[sred]<key) left=sred+1;
  31.                 else right=sred-1;          kdo++;
  32.             }
  33.             for (int j=i-1; j>=left; j--){   ///сдвиг
  34.                 b[j+1]=b[j];                kdo++;
  35.             }
  36.             b[left]=key;                    kdo++;
  37.                                                                                 for (int i=0; i<n; i++) cout<<b[i]<<' '; cout<<endl;
  38.         }
  39.     }
  40.                                                                                 for (int i=0; i<n; i++) cout<<b[i]<<' ';
  41.                                                                                 cout<<endl<<"Sravnenii : "<<ksrav<<endl<<"Deistvii : "<<kdo<<endl<<endl;
  42. }
  43. void shell(int b[], int n){
  44.     ksrav=0; kdo=0;                                                             for (int i=0; i<n; i++) cout<<b[i]<<' '; cout<<endl;
  45.     int d;                                                                      cout<<"Interval = ";
  46.     cin>>d;
  47.     while (d){                                                                  cout<<"Interval = "<<d<<endl;
  48.         for (int i=d; i<n; i++){
  49.             int key=b[i];///значение
  50.             int j=i-d;   ///индекс
  51.             while (b[j]>key&&j>=0){ksrav++;
  52.                 b[j+d]=b[j];       kdo++;
  53.                 j-=d;
  54.             }
  55.             b[j+d]=key;            kdo++;                                       //for (int i=0; i<n; i++)cout<<b[i]<<' ';cout<<endl;
  56.         }                                                                       for (int i=0; i<n; i++)cout<<b[i]<<' ';cout<<endl;
  57.         if (d==1) break;
  58.         d=d/3+1;
  59.     }
  60.                                                                                 cout<<endl<<"Sravnenii : "<<ksrav<<endl<<"Deistvii : "<<kdo<<endl<<endl;
  61. }
  62. int main()
  63. {
  64.     int n;
  65.     cout<<"Razmer massiva = ";
  66.     cin>>n;
  67.     int a[n];
  68.     srand(time(NULL));
  69.     cout<<"Ishodniy massiv :"<<endl;
  70.     for (int i=0; i<n; i++){
  71.         a[i]=n/2-rand()%n;
  72.         //a[i]=n-i;
  73.         //cin>>a[i];
  74.     }
  75.     for (int i=0; i<n; i++)cout<<a[i]<<' ';cout<<endl;
  76.     int pass=1;
  77.     while (pass>0&&pass<4){
  78.         cout<<"Kak budem sortirovat' ?"<<endl;
  79.         cout<<'\t'<<"(1)"<<' '<<"Prostie vstavki"<<endl;
  80.         cout<<'\t'<<"(2)"<<' '<<"Binarnie vstavki"<<endl;
  81.         cout<<'\t'<<"(3)"<<' '<<"Algorithm Shella"<<endl;
  82.         cin>>pass;
  83.         int b[n];
  84.         if (pass==1)    {
  85.             for (int i=0; i<n; i++)
  86.                 b[i]=a[i];
  87.             prost(b , n);
  88.         }
  89.         if (pass==2)    {
  90.             for (int i=0; i<n; i++)
  91.                 b[i]=a[i];
  92.             binar(b , n);
  93.         }
  94.         if (pass==3)    {
  95.             for (int i=0; i<n; i++)
  96.                 b[i]=a[i];
  97.             shell(b , n);
  98.         }
  99.     }
  100.     return 0;
  101. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top