Printable View
Let's assume we want to apply bitonic sorting in this example input:
12, 4, 9, 7, 5, 8, 1, 10, 4, 14, 6, 11, 7, 2, 0, 3
I admit I have no understanding of bitonic sorting algorithm, so if one wants to be scholastic, do not hesitate from being! :D
Actually my real problem is how to convert this sequence of numbers in a bitonic sequence :/
//Thanks in advance
It's meant to be used for parallel merge like sorting, except that the created subgroups alternate between ascending and descending sequences:
Links to articles:
Bitonic sorter - Wikipedia, the free encyclopedia
Bitonic Sort: Overview
As mentioned in the articles, for a single threaded environment, it's slower than a normal (bottom up) merge sort, but can be faster if used in a parallel environment. I'm not sure about a multi-threaded version, since there's only a single main memory bus, and typically the outer cache is shared between cores, so the only parallel memory operations take place in the inner cache for each core.
The bitonic sequence would be
1, 5, 7, 8, 9, 10, 12, 15, 14, 13, 11, 6, 4, 3, 2, 07
This is a good example. I had found the links you provided, but they are no good to me :)
This example matches the first example from the wiki article.
In the example you linked to, after the first pass, the first pair of the second half are descending, so the right half does not contain bitonic sub-sequences. In the case of both the wiki and overview algorithms, after the first pass, there are 4 bitonic sequence of size 4. After the second pass, there are 2 bitonic sequences of size 8. After the third pass, there is 1 bitonic sequence of size 16. After the fourth pass, the data is sorted.
update - The purpose of using bitonic sequences for a hardware based sort is that for each phase of each pass of the sort, the distance between compared values is fixed, which would reduce variation in propagation delays. I'm not sure if there's any advantage for a software based sort.Code:12 04 09 07 05 13 08 01 10 14 06 11 15 02 00 03
04 12 | 09 07 | 05 13 | 08 01 | 10 14 | 11 06 | 02 15 | 03 00
04 07 09 12 | 08 13 05 01 | 10 06 11 14 | 03 15 02 00
04 07 | 09 12 | 13 08 | 05 01 | 06 10 | 11 14 | 15 03 | 02 00
04 07 05 01 13 08 09 12 | 15 10 11 14 06 03 02 00
04 01 05 07 | 09 08 13 12 | 15 14 11 10 | 06 03 02 00
01 04 | 05 07 | 08 09 | 12 13 | 15 14 | 11 10 | 06 03 | 02 00
01 04 05 07 06 03 02 00 15 14 11 10 08 09 12 13
01 03 02 00 06 04 05 07 | 08 09 11 10 15 14 12 13
01 00 02 03 | 05 04 06 07 | 08 09 11 10 | 12 13 15 14
00 01 | 02 03 | 04 05 | 06 07 | 08 09 | 10 11 | 12 13 | 14 15
For bitonic sorting, you don't start off by making that into a bitonic sequence. That's just a step along the way, though it certainly depends on the order you do things. As a bitonic sorter is really just a static sorting network, there are a few different ways in which you can structure that sorting network.
From the point of view of understanding the algorithm, the way you need to think about it is:
If I already have two bitonic sequences, how can I merge to two to become a single monotonic sequence, in either ascending or descending direction?
You can then look at the base case where any sequence of exactly two items is already a bitonic sequence consisting of 1 item in ascending order followed by 1 item in descending order. Then you apply the recursive step.
So you never have to think about how you get to a bitonic sequence at all. You always just think of how you transform a bitonic sequence into a monotonic sequence.
I got the idea by the example I provided, but thank you for your answers :)
//post no. 3, the bitonic sequence provided is obviously wrong. (it is not the corresponding sequence for the sequence in the 1st post).