SkyHawk

Bucket Sort

Jul 6th, 2011
420
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void l_inSort(int* p,int start)
  2. {
  3.     int i = start,j;
  4.     if(!i)
  5.         return;
  6.     while(p[i]!=0)
  7.     {
  8.         j = start;
  9.         while(p[p[j]+1]<p[p[i]+1] && p[j]!=i)
  10.             j = p[j];
  11.         int t = p[p[i]];
  12.         if(j!=i)
  13.         {
  14.             p[p[i]] = p[j];
  15.             p[j] = p[i];
  16.             p[i] = t;
  17.         }
  18.         else
  19.             i = p[i];
  20.        
  21.     }
  22. }
  23.  
  24. void bucketSort(int* p,int l)
  25. {
  26.     int* mem = new int[(l<<1) + 65536];
  27.     int pos = 65536;
  28.     for(int i = 0;i<65536;++i)
  29.         mem[i] = 0;
  30.     int mask = 65535;
  31.     for(int i = 0;i<l;++i)
  32.     {
  33.         int t = mem[p[i]&mask];
  34.         mem[p[i]&mask] = pos;
  35.         mem[pos++] = t;
  36.         mem[pos++] = p[i];
  37.     }
  38.     for(int i = 0;i<65536;++i)
  39.         l_inSort(mem,i);
  40.     int j = 0;
  41.     for(int i = 0;i<65536;++i)
  42.     {
  43.         int t = mem[i];
  44.         while(t)
  45.         {
  46.             p[j++] = mem[t+1];
  47.             t = mem[t];
  48.         }
  49.     }
  50. }
RAW Paste Data