Sorting/Doubles/hash.c File Reference

Define hash to use for Bucket Sort of doubles drawn from the range [0,1]. Bucket Sort succeeds with uniform distribution since the hashing function can partition the input set of n values into n bins. The number of elements in the collection (numElements) is used to define a set of 'num' bins. More...


Functions

int numBuckets (int numElements)
 The number of buckets to use given the number of elements.
int hash (double *d)
 Hash function to identify bucket number from element.

Variables

static int num
 Computed number of bins to use for BucketSort.


Detailed Description

Define hash to use for Bucket Sort of doubles drawn from the range [0,1]. Bucket Sort succeeds with uniform distribution since the hashing function can partition the input set of n values into n bins. The number of elements in the collection (numElements) is used to define a set of 'num' bins.

Author:
George Heineman
Date:
6/15/08

Function Documentation

int hash ( double *  d  ) 

Hash function to identify bucket number from element.

Customized to properly encode elements in order within the buckets.

When range of numbers is distributed within [0,1) we subdivide into buckets of size 1/num. Thus bucket = num * (*d). Note that uniform distribution will perform better than normal distribution.

Parameters:
d value to be sorted is uniformly drawn from [0,1).

int numBuckets ( int  numElements  ) 

The number of buckets to use given the number of elements.

Parameters:
numElements number of elements in the collection to be sorted.


Variable Documentation

int num [static]

Computed number of bins to use for BucketSort.

Algorithm Development Kit 1.0