| Line 16: | Line 16: | ||
===Part 1: Transforming any sequence of numbers into a bitonic sequence=== | ===Part 1: Transforming any sequence of numbers into a bitonic sequence=== | ||
| − | It's a log2(N) algorithm where we recursively compare and swap elements 2 by 2 in a very specific manner. | + | It's a O(N*log2(N)) algorithm where we recursively compare and swap elements 2 by 2 in a very specific manner. |
For 8 values, we first perform 4 compare&swaps like this (pass 1): | For 8 values, we first perform 4 compare&swaps like this (pass 1): | ||
| Line 33: | Line 33: | ||
===Part 2: Sorting the 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. | + | Well it's another O(N*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 (pass 1): | For 8 values, we first perform 4 compares&swaps like this (pass 1): | ||
| Line 55: | Line 55: | ||
Here x0, x1, ..., xn}+ describes a set of values in ascending order and {x0, x1, ..., xn}- describes a set of values in descending order. While { {...}+, {...}- }B describes a bitonic sequence. | Here x0, x1, ..., xn}+ describes a set of values in ascending order and {x0, x1, ..., xn}- describes a set of values in descending order. While { {...}+, {...}- }B describes a bitonic sequence. | ||
| + | ===Part 1=== | ||
| + | Initial random sequence: 35, 16, 31, 4, 4, 16, 17, 12 | ||
| − | + | * Pass 1: {{16, 35}+, {31, 4}-}B, {{4, 16}+, {17, 12}-}B ← We already have 2 size 4 bitonic sequences | |
| + | |||
| + | * Pass 2: 16, 4, 31, 35, 17, 16, 4, 12 ← It's becoming somewhat random again while we're sorting the 2 size 4 bitonic sequences into a single size 8 sequence | ||
| + | |||
| + | * Pass 3: {{4, 16, 31, 35}+, {17, 16, 12, 4}-}B ← And we're done! | ||
| + | |||
| + | ===Part 2=== | ||
| + | Initial bitonic sequence from part 1: 4, 16, 31, 35, 17, 16, 12, 4 | ||
| − | + | * Pass 1: 4, 16, 12, 4, 17, 16, 31, 35 | |
| − | + | * Pass 2: 4, 4, 12, 16, 17, 16, 31, 35 | |
| − | + | * Pass 3: 4, 4, 12, 16, 16, 17, 31, 35 ← And we're done! | |
Revision as of 15:26, 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.
Contents
Quick Algorithm
Part 1: Transforming any sequence of numbers into a bitonic sequence
It's a O(N*log2(N)) algorithm where we recursively compare and swap elements 2 by 2 in a very specific manner.
For 8 values, we first perform 4 compare&swaps like this (pass 1):
Then we perform 4 compares&swaps like this (pass 2):
Finally we perform 4 compares&swaps like this (pass 3):
Part 2: Sorting the bitonic sequence
Well it's another O(N*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 (pass 1):
Then we perform 4 compares&swaps like this (pass 2):
Finally we perform 4 compares&swaps like this (pass 3):
The way I see it
Example
Here x0, x1, ..., xn}+ describes a set of values in ascending order and {x0, x1, ..., xn}- describes a set of values in descending order. While { {...}+, {...}- }B describes a bitonic sequence.
Part 1
Initial random sequence: 35, 16, 31, 4, 4, 16, 17, 12
- Pass 1: {{16, 35}+, {31, 4}-}B, {{4, 16}+, {17, 12}-}B ← We already have 2 size 4 bitonic sequences
- Pass 2: 16, 4, 31, 35, 17, 16, 4, 12 ← It's becoming somewhat random again while we're sorting the 2 size 4 bitonic sequences into a single size 8 sequence
- Pass 3: {{4, 16, 31, 35}+, {17, 16, 12, 4}-}B ← And we're done!
Part 2
Initial bitonic sequence from part 1: 4, 16, 31, 35, 17, 16, 12, 4
- Pass 1: 4, 16, 12, 4, 17, 16, 31, 35
- Pass 2: 4, 4, 12, 16, 17, 16, 31, 35
- Pass 3: 4, 4, 12, 16, 16, 17, 31, 35 ← And we're done!