# Algorithm Improvement through Performance Measurement: Part 6

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

```
Listing 3

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.

[Click image to view at full size]
Table 3: Random 8-bit Signed Elements.

[Click image to view at full size]
Figure 3

[Click image to view at full size]
Table 4: Random 16-bit Signed Elements.

[Click image to view at full size]
Figure 4

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

Quick Read

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

Quick Read

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

Quick Read

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

Quick Read

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

Quick Read

More "Best of the Web" >>