Channels ▼
RSS

C/C++

Benchmarking Block-Swapping Algorithms


Gries and Mills Block Swapping

Bentley also describes a block-swapping algorithm by Gries and Mills in his book and the article. The algorithm swaps the largest equal-sized non-overlapping blocks available at each step. The main idea is to use swap as an operation as follows from his article:

  1. A is the left subarray, B is the right subarray — that is, the starting point is AB
  2. If A is shorter, divide B into BL and BR, such that length of BR equals the length of A
  3. Swap A and BR to change ABLBR into BRBLA
  4. Recur on the two pieces of B
  5. Once A and B are of equal lengths, swap A and B

Figure 6 shows the steps:


Figure 6.

Red indicates the shorter of the two subarrays. The red subarray is A, and the blue subarray is B. The length of A is two, which is shorter than the length of B, which is five, and B is divided into BL and BR, where BR is of equal length to A. At this point BR contains elements 5 and 6. A and BR are swapped, which is shown in the second row.

In the third row, the original A subarray (elements 0 and 1) is at its final location, shown in grey. The smaller of the BL and BR is colored red, and the next level of recursion proceeds with these two subarrays. Elements 5 and 6 become the red subarray A, and the blue subarray of elements 2, 3 and 4 becomes B. Since A is shorter than B, the subarray B is split into BL and BR consisting of elements (2) and (3 and 4), respectively. In row four, subarrays A and BL are swapped. The algorithm continues to recurse, until the remaining subarrays are of the same size, at which point they are swapped. The Gries-Mills Swap non-recursive implementation is shown in Listing Two.

Listing Two: The Gries-Mills non-recursive implementation.

template< class _Type >
inline void swap( _Type* x, int a, int b, int m )
{
	while( m-- > 0 )
		exchange( x[ a++ ], x[ b++ ] );
}
template< class _Type >
inline void block_swap_Gries_and_Mills( _Type* a, int l, int m, int r )
{
	int rotdist = m - l + 1;
	int n       = r - l + 1;
	if ( rotdist == 0 || rotdist == n )  return;
	int p, i = p = rotdist;
	int j = n - p;
	while ( i != j )
	{
		if ( i > j )
		{
			swap( a, p-i, p, j );
			i -= j;
		}
		else {
			swap( a, p-i, p+j-i, i );
			j -= i;
		}
	}
	swap( a, p-i, p, i );
}

Reversal Algorithm

The third algorithm Bentley describes is the Reversal, which is the simplest. The Reversal algorithm uses rotation as the operation instead of swap. Figure 7 shows the steps:


Figure 7.

The first row is the original array, where the red and the blue subarrays are to be exchanged. In the second row, the elements of the red array are rotated. Rotation is an operation that can be done in-place for any number of elements (odd or even), reversing the order of elements within an array. In the third row, the elements of the blue subarray are rotated. Going from the third row to the last row, the entire array is rotated, resulting in the red and blue subarrays being exchanged. The implementation is shown in Listing Three.

Listing Three: Reversal Algorithm.

// reverse/mirror a range from l to r, inclusively, in-place
template< class _Type >
inline void reversal( _Type* a, int l, int r )
{
	while( l < r )	exchange( a[ l++ ], a[ r-- ] );
}
// Swaps two sequential subarrays ranges a[ l .. m ] and a[ m + 1 .. r ]
template< class _Type >
inline void block_exchange_reversal( _Type* a, int l, int m, int r )
{
	reversal( a, l,     m );
	reversal( a, m + 1, r );
	reversal( a, l,     r );
}

The inverse variation on this method rotates the whole array, followed by the rotations of the two subarrays, as shown in Figure 8:


Figure 8.

Going from the first row to the second, the entire array is rotated. At this point, the blue and red subarrays are in their proper places, but each are in reverse order. In the third row, the blue subarray is rotated. In the last row, the red subarray is rotated. The result is a red and blue block exchange. Listing Four shows an implementation of this method.

Listing Four: Reversal Algorithm in Reverse.

template< class _Type >
inline void block_exchange_reversal_reverse_order( _Type* a, int l, int m, int r )
{
	reversal( a, l, r );
	int m_in_destination = r - ( m - l + 1 );
	reversal( a, l, m_in_destination        );
	reversal( a,    m_in_destination + 1, r );
}


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