#header-inner {background-position: right !important; width: 100% !important;}


Bitonic Sorting Net.

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


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.


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