Advertisement
patryk178

Counting sort with negative numbers

Mar 6th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int mini = 0;
  6. int maxi = 0;
  7. int *koniec;
  8. void sortowanie(int T[], int n)
  9. {
  10.     int ile = (maxi-mini)+1;
  11.     int *zliczanie = new int [ile];
  12.     int *suma = new int [ile];
  13.     koniec = new int [n];
  14.  
  15.     for(int i=0;i<ile;i++)
  16.     {
  17.         zliczanie[i]=0;
  18.     }
  19.  
  20.     for(int i=0;i<ile;i++)
  21.     {
  22.  
  23.         for(int j=0;j<ile-1;j++)
  24.         {
  25.             if(T[j]-mini==i)zliczanie[i]++;
  26.         }
  27.     }
  28.    
  29.     suma[0] = zliczanie[0];
  30.  
  31.     for(int i=0;i<ile;i++)
  32.     {
  33.         suma[i+1] = suma[i]+zliczanie[i+1];
  34.     }
  35.     for(int i=0;i<n;i++)
  36.     {
  37.         suma[T[i]-mini]--;
  38.         koniec[suma[T[i]-mini]]=T[i];
  39.     }
  40.  
  41.     for(int i=0;i<n;i++)
  42.     {
  43.         cout<<T[i]<<" ";
  44.         cout<<koniec[i]<<" "<<endl;
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     int n;
  51.     cout << "Ile liczb: ";cin>>n;
  52.  
  53.     int T[n];
  54.     //int *T = new int [n];
  55.     for(int i = 0;i<n;i++)
  56.     {
  57.         cin>>T[i];
  58.     }
  59.  
  60.     mini = T[0];
  61.     maxi = T[0];
  62.     for(int i=0;i<n;i++)
  63.     {
  64.         if(T[i]>maxi)maxi=T[i];
  65.         else if(T[i]<mini) mini = T[i];
  66.     }
  67.  
  68.     sortowanie(T,n);
  69.  
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement