9/10/14

Bitonic Sorting Net.

Sorting network for bitonic sequences can be constructed from 'half-cleaners'.

Half-Cleaner.

For size n input sequence, i-th input is connected with comparator with i + n/2 input,
for i = 1, 2, ... , n/2. We'll assume than n is even.



Half-Cleaner.



Bitonic Sorter.



Bitonic Sorter Construction Algorithm.


Using a Half-Cleaner & two smaller Bitonic Sorters we can Create a larger Bitonic Sorter recurrentially as shown on above image.





a Complete Bitonic Sorter Example.



Bitonic Sorting has use in Sorting with time complexity of O(log2 n) - a 'good behavior' for parallel sorting algorithms.

For Sequential Sorting Algorithms, 'good behavior' is time complexity of O(n · log n).


Source: [4], Wikipedia.

See also: Sorting Nets, Comparing Net, Bitonic Sequence, Bitonic Sorting in Cryptography.

No comments:

Post a Comment