Wednesday, April 9, 2014

Linear sort for range of numbers in C

#include <stdio.h>
#include <stdlib.h>

/* Sorting numbers in a defined range 0 ... N-1 with
 * no repeats
 * Inspired from Programming Pearls : Jon Bently
 * O(n) linear cost.
 */

#define N           10000000
#define BITSPERWORD 32
#define SHIFT        5
#define TOPVAL      (1+N/BITSPERWORD)
#define MASK        0x1f
/* Above is same as mod operation, i%32 == i&5 */
/* Complete intent of mask is to guard against value
 * of 32 or above.
 */
#define set(i)    (bitvec[i >> SHIFT] |= (1<<(i&MASK)))
#define test(i)   (bitvec[i >> SHIFT] & (1<<(i&MASK)))

/* Printing routine */
void spill(int *a, int sz)
{
    int indx;
    for (indx = 0 ; indx < sz; indx++)
    {
        printf("%d ", a[indx]);
    }
    printf("\n");
}

void bitsort(int *a, int sz)
{
  int maxval = 0;
  int indx   = 0;
  int i = 0;

  int *bitvec = calloc(TOPVAL, sizeof(int));

  for (indx = 0; indx < sz ; indx++)
  {
     if (a[indx] > maxval) maxval = a[indx];
     set(a[indx]);
  }

  for (indx = 0; indx <= maxval ; indx++)
  {
     if (test(indx))
        a[i++] = indx;
  }

  free(bitvec);
}

int main()
{
  int arr[] = {205, 10, 7, 5, 9, 8, 1, 2, 100};
  bitsort(arr, 9);
  spill(arr,9);
}

No comments:

Post a Comment