Signed
Signed integers use 2's complement format shown below, with the binary representation on the left and its decimal value on the right:
01111111<sub>b</sub> 127 01111110<sub>b</sub> 126 01111101<sub>b</sub> 125 …. 00000001<sub>b</sub> 1 00000000<sub>b</sub> 0 11111111<sub>b</sub> -1 11111110<sub>b</sub> -2 11111101<sub>b</sub> -3 … 10000011<sub>b</sub> -125 10000010<sub>b</sub> -126 10000001<sub>b</sub> -127 10000000<sub>b</sub> -128
Note that the most-significant-bit (MSB) serves as the sign bit. However, its meaning is opposite of what is needed for sorting [2]. The implementations in Listings 1 and 2 work only for unsigned numbers. Radix sorting algorithms for unsigned numbers in [1] and [2] were extended to handle sorting of signed numbers by processing the most-significant-bit in [1] and the most-significant-digit in [2] as a special case. However, a different method is needed here, since the entire value of an array element is processed in a single step by the Counting Sort algorithm.
One possible way to handle signed numbers efficiently is to treat them as positive numbers and then adjust the algorithm where necessary. When we treat signed 8-bit numbers as unsigned, the value of -128 becomes 128, the value -127 becomes 129, the value -126 becomes 130, and so on until the value of -1 becomes 255. This is exactly the same as adding 256 to all of the negative numbers. Listing 3 shows the signed 8-bit and 16-bit Counting Sort implementation, where in the second for loop the array elements are first converted to unsigned 8-bit values and then used for counting.
// Copyright(c), Victor J. Duvanenko, 2010
// Listing 3
inline void CountSortInPlace( char* a, unsigned long a_size )
{
if ( a_size < 2 ) return;
const unsigned long numberOfCounts = 256;
const unsigned long maxChar = 127;
// one count for each possible value of an 8-bit element (0-255)
unsigned long count[ numberOfCounts ] = { 0 };
// Scan the array and count the number of times each value appears
for( unsigned long i = 0; i < a_size; i++ )
count[ (unsigned char)( a[ i ]) ]++; // treat the signed value as if it was unsigned
// Fill the array with the number of 0's that were counted, followed by the number of 1's, and then 2's and so on
unsigned long n = 0;
for( unsigned long i = maxChar+1; i < numberOfCounts; i++ ) // -128 to -1
for( unsigned long j = 0; j < count[ i ]; j++, n++ )
a[ n ] = (char)i;
for( unsigned long i = 0; i <= maxChar; i++ ) // 0 to 127
for( unsigned long j = 0; j < count[ i ]; j++, n++ )
a[ n ] = (char)i;
}
inline void CountSortInPlace( short* a, unsigned long a_size )
{
if ( a_size < 2 ) return;
const unsigned long numberOfCounts = 65536;
const unsigned long maxShort = 32767;
// one count for each possible value of an 8-bit element (0-255)
unsigned long count[ numberOfCounts ] = { 0 };
// Scan the array and count the number of times each value appears
for( unsigned long i = 0; i < a_size; i++ )
count[ (unsigned short)( a[ i ]) ]++;
// Fill the array with the number of 0's that were counted, followed by the number of 1's, and then 2's and so on
unsigned long n = 0;
for( unsigned long i = maxShort+1; i < numberOfCounts; i++ ) // -32768 to -1
for( unsigned long j = 0; j < count[ i ]; j++, n++ )
a[ n ] = (short)i;
for( unsigned long i = 0; i <= maxShort; i++ ) // 0 to 32767
for( unsigned long j = 0; j < count[ i ]; j++, n++ )
a[ n ] = (short)i;
}
The -128 count is now stored in count[128], and -127 count is stored in count[129], and so on until the -1 count is stored in count[255]. These counts need to be processed starting from the smallest value (the count of -128 value), which is in count[128]. The third for loop processes the negative values starting at -128 and incrementing toward -1. The fourth loop processed the positive values starting at 0 and incrementing toward 127. The advantage of this implementation is that it required no additional arithmetic during counting, and no additional arithmetic during the writing step. Thus, signed numbers are expected to be processed without any performance penalties.
Tables 3 and 4, as well as Figures 3 and 4 show performance measurements of various sorting algorithms for 8-bit and 16-bit signed numbers.
Performance measurements for sorting of arrays of signed 8-bit and 16-bit numbers is very similar to that of unsigned 8-bit and 16-bit, validating that the difference in the implementation for handling signed numbers did not cost in performance. Using array initialization in the signed implementation resulted in higher performance than using a for loop.
