Radix sort for float numbers

Radix sort is a linear sorting algorithm. However, it is commonly applied to integral values. This article shows, that - under certain circumstances - radix sort can be applied to floating point values as well.

How radix sort works on integral values

To understand the method of radix sort, we first assume, that all our numbers are nonnegative and have an equal number of digits. Eventually, the numbers are filled with leading zeroes.

Consider the following sequence of numbers and how it can be written, so that all numbers have equally many digits.

Now, we define a simple operation on a sequence of numbers: denotes a sorting operation, that sorts the numbers stable according to the -th digit. Note that we begin counting the digits at the last digit. That is, the last digit, has index 0, the pre-last has index 1, and so on. For example, digit 2 of the number 19873 is 8.

Stable means the following: If an item has the same -th digit as and comes before in the argument of , then in the result, comes before .

As said, sorts the sequence stable according to digit . As an example, we consider the following:

As you can see, i write instead of . It is easier to read.

Now, consider the following: If we first sort the numbers according to digit 0, then according to digit 1, then according to digit 2, and so on, we get a sorted sequence:

Let me illustrate this by the above example:

As you see, the final sequence is sorted. Of course, this is no proof, but it makes it a bit clearer that it works. The proof itself is left to the reader - it is not too complicated.

It is essential, that is a stable sort.

If we now code our integer values into binary, we can easily radix-sort them binary digit by binary digit. That is, for each digit, we first look, how many of the numbers have -th digit 0, and how many have -th digit 1. Then, we distribute the numbers according to their -th digit into bin 0 or bin 1.

How can radix sort be applied on floating point values?

Again, we assume, that we have no negative numbers.

32-bit-floating point values are stored the foolowing way:

The first bit denotes the sign, the second eight bits denote the mantissa, and the remaining bits stand for the decimal places. For more information, visit Wikipedia or this article.

The point is, that the binary representation of nonnegative floats and integers have a nice property. If you take this representation, you can treat the number, as if it was an integer.

That means, if you treat the digits like an integer, comparisons yield the same result as if you would treat them like floats.

For that reason, we are able to treat the floating point values as integers and then doing a radix sort as explained above.

This leads to the following C++-Code:

// Radix sort that treats floats as ints and sorts them
for (int i=0; i < 32; ++i){
	unsigned int radix=(1 << i);
	
	float zwarray[count];
	
	// count how many 0-value-radixes we have
	int count0=0;
	int count1=0;

	for (int j=0; j < count; ++j){
		if (!((*(int*)&(array[j]))&radix)){
			++count1;
		}
	}
	
	for (int j=0; j < count; ++j){
		if ((*(int*)&(array[j]))&radix){
			zwarray[count1]=array[j];
			++count1;
		}
		else {
			zwarray[count0]=array[j];
			++count0;
		}
	}
	
	for (int j=0; j < count; ++j){
		array[j]=zwarray[j];
	}
	
}

array is the array to be sorted. count is the number of elements in array.

Consider the expression ((*(int*)&(array[j]))&radix). It checks, wether the bit at position i is set or not.

Conclusion

The above implementation has some weak points. It's runtime is where is the number of elements to be sorted. More precisely, it traverses the array 64 times, since we assume 32 bit and we need 2 passes in each loop.

One optimisation could be, that we do not consider only one bit, but we consider a whole byte as a digit. If we do so, we only need 8 traversals, since we have 4 byte and again 2 passes in each loop. A (problably) solvable problem when using whole bytes, is that we have to do a more sophisticated counting.

Comments

• disclaimer
• about
• administration