Advertisement
TheMagnusRex

Count sort (сортировка подсчётом) в общем случае

Jan 25th, 2017
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.22 KB | None | 0 0
  1. #include <iostream>
  2. #include "random"
  3.  
  4. using namespace std;
  5.  
  6. void feel(int *a,int n){
  7.     for (int i=0;i<n;i++){
  8.         a[i]=rand()%100-50;
  9.     }
  10. }
  11.  
  12. void show(int *a,int n){
  13.     for (int i=0;i<n;i++){
  14.         cout<<a[i]<<" ";
  15.     }
  16.     cout<<endl;
  17. }
  18. int maximus(int *a, int n){
  19.     int x=a[0];
  20.     for(int i=1;i<n;i++){
  21.         if(a[i]>x){
  22.             x=a[i];
  23.         }
  24.     }
  25.     return x;
  26. }
  27.  
  28. int minimus(int *a,int n){
  29.     int x=a[0];
  30.     for(int i=1;i<n;i++){
  31.         if(a[i]<x){
  32.             x=a[i];
  33.         }
  34.     }
  35.     return x;
  36. }
  37.  
  38. int main()
  39. {
  40.     int k=0;
  41.     int n;
  42.     cin>>n;
  43.     int a[n];
  44.     feel(a,n);
  45.     show(a,n);
  46.     int min=minimus(a,n);
  47.     int max=maximus(a,n);
  48.     if (min>=0&&max>=0){
  49.         int r=max-min;
  50.         int c[r];
  51.         for(int i=0;i<r;i++){
  52.             c[i]=0;
  53.         }
  54.         for (int i=0;i<n;i++){
  55.             c[a[i]]++;
  56.         }
  57.         for (int i=0;i<r;i++){
  58.             while(c[i]!=0){
  59.                 a[k]=i;
  60.                 k++;
  61.                 c[i]--;
  62.             }
  63.         }
  64.     }
  65.     if(min<0&&max<=0){
  66.         int r=max-min;
  67.         int c[r];
  68.         for(int i=0;i<r;i++){
  69.             c[i]=0;
  70.         }
  71.         for (int i=0;i<n;i++){
  72.             c[-a[i]]++;
  73.         }
  74.         for (int i=r-1;i!=0;i--){
  75.             while(c[i]!=0){
  76.                 a[k]=-i;
  77.                 k++;
  78.                 c[i]--;
  79.             }
  80.         }
  81.     }
  82.     if(min<0&&max>0){
  83.         int cp[max+1];
  84.         int co[-min+1];
  85.         for(int i=0;i<max+1;i++){
  86.             cp[i]=0;
  87.         }
  88.         for(int i=0;i<-min+1;i++){
  89.             co[i]=0;
  90.         }
  91.         for (int i=0;i<n;i++){
  92.             if (a[i]>=0){
  93.                 cp[a[i]]++;
  94.             }
  95.             else{
  96.                 co[-a[i]]++;
  97.             }
  98.         }
  99.         show(cp,max+1);
  100.         show(co,-min+1);
  101.         for(int i=-min;i!=0;i--){
  102.             while (co[i]!=0){
  103.                 a[k]=-i;
  104.                 k++;
  105.                 co[i]--;
  106.             }
  107.         }
  108.         for (int i=0;i<max+1;i++){
  109.             while (cp[i]!=0){
  110.                 a[k]=i;
  111.                 k++;
  112.                 cp[i]--;
  113.             }
  114.         }
  115.     }
  116.     show(b,n);
  117.     return 0;
  118.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement