SkyHawk

Radix Sort

Jul 6th, 2011
487
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <limits.h>
  2.  
  3. void countSort(int* p, int* res, int l, int k)
  4. {
  5.     k*=8;
  6.     int mask = 255 << k;
  7.     int* ar = new int[257];
  8.     for(int i = 0;i<257;++i)
  9.         ar[i] = 0;
  10.     ++ar;
  11.     for(int i = 0;i<l;++i)
  12.         ar[(p[i]&mask)>>k]++;
  13.     for(int i = 0;i<255;++i)
  14.         ar[i+1] += ar[i];
  15.     --ar;
  16.     for(int i = 0;i<l;++i)
  17.     {
  18.         res[ar[(p[i]&mask)>>k]] = p[i];
  19.         ++ar[(p[i]&mask)>>k];
  20.     }
  21. }
  22.  
  23. void radixSort(int* p,int l)
  24. {
  25.     int* t = new int[l];
  26.     countSort(p,t,l,0);
  27.     countSort(t,p,l,1);
  28.     countSort(p,t,l,2);
  29.     countSort(t,p,l,3);
  30. }
RAW Paste Data