From Wakapon
| Line 22: | Line 22: | ||
For 8 values, we first compare 4 values like this: | For 8 values, we first compare 4 values like this: | ||
| + | [[File:Example.jpg|thumbnail]] | ||
Revision as of 14:39, 11 September 2015
I wanted to write a short explanation about bitonic sort because it's simple as hell but no one does a good job at explaining it correctly.
You can find the video explanation here https://www.youtube.com/watch?v=GEQ8y26blEY but it's a bit tedious so to sum up the algorithm, here's what you need to know:
- A bitonic sequence is a sequence of numbers that can be ordered as first ascending then descending (or the opposite)
- For example: (1, 2, 3, 4) followed by (4,3,2,1) is bitonic.
- The bitonic sort algorithm works in 2 parts:
- (1) First, you need to transform any random sequence of numbers into a bitonic sequence
- (2) Second, you can then sort the bitonic sequence in ascending order
And that is all there is to it! Now let's see how to execute the 2 parts of the algorithm.
Part 1: Transforming any sequence of numbers into a bitonic sequence
Part 2: Sorting the bitonic sequence
Well it's another log2(N) algorithm as in part 1. You'll need to swap numbers log2(N) times.
For 8 values, we first compare 4 values like this:
