Channels ▼
RSS

Design

Algorithm Improvement through Performance Measurement: Part 4


Signed

Signed integers use 2's complement format shown below, with the binary representation on the left and its decimal value on the right:

Note that the most-significant-bit (MSB) serves as the sign bit. However, its meaning is opposite of what is needed for sorting [3]. The implementations in Listings 1, 2, and 3 work only for unsigned numbers. Radix sorting methods for unsigned numbers in [1] and [3] were extended to handle sorting of signed numbers by processing the most-significant-bit in [1] and the most-significant-digit in [3] as a special case. The same method is used in the signed sorting algorithm implementation in Listing 4.


// Copyright(c), Victor J. Duvanenko, 2009

// A set of logical right shift functions to work-around the C++ issue of performing an arithmetic right shift
// for >>= operation on signed types.
inline char logicalRightShift( char a, unsigned long shiftAmount )
{
	return (char)(((unsigned char)a ) >> shiftAmount );
}
inline unsigned char logicalRightShift_ru( char a, unsigned long shiftAmount )
{
	return (((unsigned char)a ) >> shiftAmount );
}
inline short logicalRightShift( short a, unsigned long shiftAmount )
{
	return (short)(((unsigned short)a ) >> shiftAmount );
}
inline unsigned short logicalRightShift_ru( short a, unsigned long shiftAmount )
{
	return (((unsigned short)a ) >> shiftAmount );
}
inline long logicalRightShift( long a, unsigned long shiftAmount )
{
	return (long)(((unsigned long)a ) >> shiftAmount );
}
inline unsigned long logicalRightShift_ru( long a, unsigned long shiftAmount )
{
	return (((unsigned long)a ) >> shiftAmount );
}
inline __int64 logicalRightShift( __int64 a, unsigned long shiftAmount )
{
	return (__int64)(((unsigned __int64)a ) >> shiftAmount );
}
inline unsigned __int64 logicalRightShift_ru( __int64 a, unsigned long shiftAmount )
{
	return (((unsigned __int64)a ) >> shiftAmount );
}
template< unsigned long PowerOfTwoRadix, class _Type >
inline unsigned long extractDigitNegate( _Type a, _Type bitMask, unsigned long shiftRightAmount )
{
	unsigned long digit = (unsigned long)logicalRightShift_ru((_Type)( a & bitMask ), 
                          shiftRightAmount );    // extract the digit we are sorting based on
	digit ^= ( PowerOfTwoRadix >> 1 );
	return digit;
}
template< unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold, class _Type >
inline void _RadixSort_StableSigned_PowerOf2Radix( _Type* a, _Type* b, long last, _Type bitMask, unsigned long shiftRightAmount, bool inputArrayIsDestination )
{
	const unsigned long numberOfBins = PowerOfTwoRadix;
	unsigned long count[ numberOfBins ];

	for( unsigned long i = 0; i < numberOfBins; i++ )
		count[ i ] = 0;
	for ( long _current = 0; _current <= last; _current++ )	
                  // Scan the array and count the number of times each value appears
		count[ extractDigitNegate< PowerOfTwoRadix >( a[ _current ], 
                                        bitMask, shiftRightAmount ) ]++;

	long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ];
	startOfBin[ 0 ] = endOfBin[ 0 ] = 0;
	for( unsigned long i = 1; i < numberOfBins; i++ )
		startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ];
	for ( long _current = 0; _current <= last; _current++ )
		b[ endOfBin[ extractDigitNegate< PowerOfTwoRadix >( a[ _current ], bitMask,
                                   shiftRightAmount ) ]++ ] = a[ _current ];

	bitMask = logicalRightShift( bitMask, Log2ofPowerOfTwoRadix );
	if ( bitMask != 0 )    // end recursion when all the bits have been processes
	{
		if ( shiftRightAmount >= Log2ofPowerOfTwoRadix )
                                      shiftRightAmount -= Log2ofPowerOfTwoRadix;
		else												shiftRightAmount  = 0;
		inputArrayIsDestination = !inputArrayIsDestination;
		for( unsigned long i = 0; i < numberOfBins; i++ )
		{
			long numOfElements = endOfBin[ i ] - startOfBin[ i ];
			if ( numOfElements >= Threshold )
				_RadixSort_StableUnsigned_PowerOf2Radix_2< PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &b[ startOfBin[ i ]], &a[ startOfBin[ i ]], numOfElements - 1, bitMask, shiftRightAmount, inputArrayIsDestination );
			else {
		insertionSortSimilarToSTLnoSelfAssignment( &b[ startOfBin[ i ]], numOfElements );
				if ( inputArrayIsDestination )
					for ( long j = startOfBin[ i ]; j < endOfBin[ i ]; j++ )	// copy from external array back into the input array
						a[ j ] = b[ j ];
			}
		}
	}
	else {	// Done with recursion copy all of the bins
		if ( !inputArrayIsDestination )
			for ( long _current = 0; _current <= last; _current++ )	
                                                        // copy from external array back into the input array
				a[ _current ] = b[ _current ];
	}
}
template< class _Type >
inline void RadixSortMSDStablePowerOf2Radix_signed( _Type* a, _Type* b, unsigned long a_size )
{
	const unsigned long Threshold             = 100;
	const unsigned long PowerOfTwoRadix       = 256;
	const unsigned long Log2ofPowerOfTwoRadix =   8;

	unsigned long shiftRightAmount = sizeof( _Type ) * 8 - Log2ofPowerOfTwoRadix;
	_Type bitMask = (_Type)( ((_Type)( PowerOfTwoRadix - 1 )) << shiftRightAmount );	// bitMask controls/selects how many and which bits we process at a time

	if ( a_size >= Threshold )	_RadixSort_StableSigned_PowerOf2Radix< PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( a, b, a_size - 1, bitMask, shiftRightAmount, false );
	else						insertionSortSimilarToSTLnoSelfAssignment( a, a_size );
}

Listing 4

This implementation works for various sizes of signed numbers, such as char, short, int, long, and int64 data types. The main idea is to invert the MSB of signed numbers and then sort based on the resulting bit or digit, but only for the most-significant bit or digit, and treat the rest of the bits or digits as unsigned.

In Listing 4 the top-level template function RadixSortMSDStablePowerOf2Radix_signed<>() calls the template function _RadixSortMSDStablePowerOf2Radix_signed<>() which uses extractDigitNegate<>() template function to extract the MSD and then invert its upper bit. For the next level of recursion _RadixSort_StableUnsigned_PowerOf2Radix_2<>() template function is called (in Listing 3), which processes the next digit (as well as the rest of the digits) as unsigned by calling itself recursively.


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