Channels ▼
RSS

Parallel

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.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 

Video