home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
listings
/
v_11_02
/
1102090a
< prev
next >
Wrap
Text File
|
1992-12-07
|
2KB
|
83 lines
/*
*
* Bose-Nelson algorithm for generating sorting
* networks. Calling bose(n) generates a network
* to sort n items. See R. C. Bose & R. J. Nelson,
* "A Sorting Problem", JACM Vol. 9, Pp. 282-296.
*/
bose(n)
int n;
{
Pstar(1, n); /* sort the sequence {X1,...,Xn} */
}
P(i, j)
int i, j;
{
printf("swap(%d, %d);\n", i, j);
}
Pstar(i, m)
int i; /* value of first element in sequence */
int m; /* length of sequence */
{
int a;
if(m > 1)
{
/*
* Partition into 2 shorter sequences,
* generate a sorting method for each,
* and merge the two sub-networks.
*/
a = m/2;
Pstar(i, a);
Pstar((i + a), (m - a));
Pbracket(i, a, (i + a), (m - a));
}
}
Pbracket(i, x, j, y)
int i; /* value of first element in sequence 1 */
int x; /* length of sequence 1 */
int j; /* value of first element in sequence 2 */
int y; /* length of sequence 2 */
{
int a, b;
if(x == 1 && y == 1)
P(i, j); /* 1 comparison sorts 2 items */
else if(x == 1 && y == 2)
{
/*
* 2 comparisons inserts an item into an
* already sorted sequence of length 2.
*/
P(i, (j + 1));
P(i, j);
}
else if(x == 2 && y == 1)
{
/* As above, but inserting j */
P(i, j);
P((i + 1), j);
}
else
{
/*
* Recurse on shorter sequences, attempting
* to make the length of one subsequence odd
* and the length of the other even. If we
* can do this, we eventually merge the two.
*/
a = x/2;
b = (x & 1) ? (y/2) : ((y + 1)/2);
Pbracket(i, a, j, b);
Pbracket((i + a), (x - a), (j + b), (y - b));
Pbracket((i + a), (x - a), j, b);
}
}