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!
Actually my real problem is how to convert this sequence of numbers in a bitonic sequence :/
//Thanks in advance
Last edited by std10093; 06-25-2013 at 06:35 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
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.
Last edited by rcgldr; 06-25-2013 at 07:23 PM.
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
Last edited by std10093; 06-25-2013 at 07:48 PM.
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
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
Last edited by rcgldr; 06-25-2013 at 08:53 PM.
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.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
I got the idea by the example I provided, but thank you for your answers
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
//post no. 3, the bitonic sequence provided is obviously wrong. (it is not the corresponding sequence for the sequence in the 1st post).
Code - functions and small libraries I use
It’s 2014 and I still use printf() for debugging.
"Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson
