#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);
}
#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