Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

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 );
}
```

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.