From Wakapon
Jump to: navigation, search
Line 21: Line 21:
 
Well it's another log2(N) algorithm as in part 1. You'll need to swap numbers log2(N) times.
 
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:
+
For 8 values, we first perform 4 compares&swaps like this:
[[File:Example.jpg|thumbnail]]
+
 
 +
[[File:BitonicCompare0.png]]
 +
 
 +
Then we perform 4 compares&swaps like this:
 +
 
 +
[[File:BitonicCompare1.png]]

Revision as of 14:45, 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 perform 4 compares&swaps like this:

BitonicCompare0.png

Then we perform 4 compares&swaps like this:

BitonicCompare1.png