Information Technology Reference
In-Depth Information
0
4
1
5
2
6
3
7
0
1
4
2
5
3
6
7
0
1
2
4
3
5
6
7
0
1
2
3
4
5
6
7
Figure 7.17
The shuffle permutation can be realized by a series of swaps of the contents of cells.
The cells between which swaps are done have a heavy bar above them. The result of swapping cells
of one row is shown in the next higher row, so that the top row contains the result of shuffling the
bottom row.
{
}
with the same value.) When this is done, the sequence
0, 1, 2, 3, 4, 5, 6, 7
is mapped to the
{
}
sequence
, the unshuffled sequence, as shown in Fig.
7.18
.Theinteger
b
is mapped to the integer
a
whose binary representation is that of
b
shifted cyclically right
by one position. For example, position 1 (001) is mapped to position 4 (100) and position 6
(110) is mapped to position 3 (011).
Since bubble sort is a stable sorting algorithm, we use it to realize the unshuffle permuta-
tion. (See Section
7.5.2
.) In each phase keys (binary tuples) are compared based on their least
significant bits. In the first phase values in positions
i
and
i
+
1arecomparedfor
i
even. The
next comparison is between such pairs for
i
odd. Comparisons of this form continue, alternat-
ing between even and odd values for
i
, until the sequence is sorted. Since the first phase has
no effect on the integers
0, 2, 4, 6, 1, 3, 5, 7
{
0, 1, 2,
...
,
n
ā
}
, it is not done. Subsequent phases are shown in
Fig.
7.18
. Pairs that are compared are connected by a light line; a darker line joins pairs whose
values are swapped. (See Problem
7.16
.)
We now show how to implement efficiently a fully normal ascending algorithm on a linear
array. (See Fig.
7.19
.) Let the
exchange locations
of the linear array be locations
i
and
i
+
1
of the array for
i
even. Only elements in exchange locations are swapped. Swapping between
the first dimension of the hypercube is done by swaps across exchange locations. To simulate
exchanges across the second dimension, perform a shuffle operation (by reversing the order of
the operations of Fig.
7.18
) on each group of four elements. This places into exchange locations
elements whose original indices differed by two. Performing a shuffle on eight, sixteen, etc.
1
0
2
4
6
1
3
5
7
0
2
4
1
6
3
5
7
0
2
1
4
3
6
5
7
0
1
2
3
4
5
6
7
Figure 7.18
An unshuffle operation is obtained by bubble sorting the integers
{
0, 1, 2,
...
,
nā
1
}
based on the value of their least significant bits. The cells with bars over them are compared.
The first set of comparisons is done on elements in the bottom row. Those pairs with light bars
contain integers whose values are in order.
Search WWH ::
Custom Search