Advertisement
NickG

radix sort2

May 10th, 2012
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. void radixsort(int array[], int size) {
  2.  
  3. //Set max equal to the greatest element of the array
  4. int max = 0;
  5. for (int i = 0; i < size; i++) {
  6.    if (array[i] > max)
  7.       max = array[i];
  8.    }
  9.  
  10. for(int pow10=1; max != 0; max/=10, pow10*=10) {
  11.    int buffer[size], blarg[size], bucket[10] = {0};
  12.  
  13.       //This might improve speed
  14.       for (int i = 0; i < size; i++)
  15.          blarg[i]=(array[i] / pow10) % 10;
  16.  
  17.       //Calculate the bucket numbers
  18.       for (int i = 0; i < size; i++)
  19.          bucket[blarg[i]]++;
  20.      
  21.       //Sum the bucket numbers
  22.       for (int i = 1; i<10; i++)
  23.          bucket[i] += bucket[i - 1];
  24.  
  25.       //Bucket sort the array into a buffer
  26.       for  (int i = size - 1; i >= 0; i--)
  27.          buffer[--bucket[(blarg[i]] = array[i];
  28.  
  29.       //Move the sorted elements back into array
  30.       for (int i = 0; i < size; i++)
  31.          array[i] = buffer[i];
  32.   }
  33. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement