Bitonic Sort - Revision history

Patapom at 15:26, 11 September 2015

2015-09-11T15:26:34Z

Patapom at 14:45, 11 September 2015

2015-09-11T14:45:22Z

Patapom at 14:26, 11 September 2015

2015-09-11T14:26:05Z

Patapom at 14:17, 11 September 2015

2015-09-11T14:17:54Z

Patapom at 14:05, 11 September 2015

2015-09-11T14:05:06Z

Patapom at 13:58, 11 September 2015

2015-09-11T13:58:15Z

Patapom at 13:48, 11 September 2015

2015-09-11T13:48:12Z

Patapom at 13:45, 11 September 2015

2015-09-11T13:45:09Z

Patapom at 13:39, 11 September 2015

2015-09-11T13:39:25Z

Patapom at 13:15, 11 September 2015

2015-09-11T13:15:56Z

@@ Line 83: / Line 83: @@
 * 1st stage consists of:
-** 8 groups one length 1 compares&swaps ('''C&S'''). Even groups are in ascending order, odd groups are in descending order.
+** 8 groups of one length-1 compares&swaps ('''C&S'''). Even groups are in ascending order, odd groups are in descending order.
 * 2nd stage consists of:
-** 4 groups of two length 2 C&S. Even groups are in ascending order, odd groups are in descending order.
+** 4 groups of two length-2 C&S. Even groups are in ascending order, odd groups are in descending order.
-** 4 groups of two length 1 C&S. Even groups are in ascending order, odd groups are in descending order.
+** 4 groups of two length-1 C&S. Even groups are in ascending order, odd groups are in descending order.
 * 3rd stage consists of:
-** 2 groups of four length 4 C&S. Even groups are in ascending order, odd groups are in descending order.
+** 2 groups of four length-4 C&S. Even groups are in ascending order, odd groups are in descending order.
-** 2 groups of four length 2 C&S. Even groups are in ascending order, odd groups are in descending order.
+** 2 groups of four length-2 C&S. Even groups are in ascending order, odd groups are in descending order.
-** 2 groups of four length 1 C&S. Even groups are in ascending order, odd groups are in descending order.
+** 2 groups of four length-1 C&S. Even groups are in ascending order, odd groups are in descending order.
 In total, there are 8 + (8+8) + (8+8+8) possible compare&swaps or N + (2*N) + (3*N) + ... + (log(N)*N) = (log(N)*(log(N)+1) * N / 2) operations hence the O(N log²N) notation.

@@ Line 16: / Line 16: @@
 ===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.
+It's a O(N*log²(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):
@@ Line 33: / Line 33: @@
 ===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.
+Well it's another O(N*log²(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):
@@ Line 46: / Line 46: @@
 [[File:BitonicCompare2.png]]
@@ Line 72: / Line 69: @@
 * Pass 3: 4, 4, 12, 16, 16, 17, 31, 35  ← And we're done!

@@ Line 16: / Line 16: @@
 ===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):
@@ Line 33: / Line 33: @@
 ===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):
@@ 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.
-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
-After part 1 pass 1: {{16, 35}+, {31, 4}-}B, {{4, 16}+, {17, 12}-}B  ← We already have 2 size 4 bitonic sequences
+* Pass 1: 4, 16, 12, 4, 17, 16, 31, 35
-After part 1 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 2: 4, 4, 12, 16, 17, 16, 31, 35
-After part 1 pass 3: {{4, 16, 31, 35}+, {17, 16, 12, 4}-}B ← And we're done!
+* Pass 3: 4, 4, 12, 16, 16, 17, 31, 35  ← And we're done!

@@ Line 18: / Line 18: @@
 It's a 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:
+For 8 values, we first perform 4 compare&swaps like this (pass 1):
 [[File:BitonicBuild0.png]]
-Then we perform 4 compares&swaps like this:
+Then we perform 4 compares&swaps like this (pass 2):
 [[File:BitonicBuild1.png]]
-Finally we perform 4 compares&swaps like this:
+Finally we perform 4 compares&swaps like this (pass 3):
 [[File:BitonicBuild2.png]]
@@ Line 35: / Line 35: @@
 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:
+For 8 values, we first perform 4 compares&swaps like this (pass 1):
 [[File:BitonicCompare0.png]]
-Then we perform 4 compares&swaps like this:
+Then we perform 4 compares&swaps like this (pass 2):
 [[File:BitonicCompare1.png]]
-Finally we perform 4 compares&swaps like this:
+Finally we perform 4 compares&swaps like this (pass 3):
 [[File:BitonicCompare2.png]]
@@ Line 52: / Line 52: @@
 ==Example==

@@ Line 13: / Line 13: @@
 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==
+==Quick Algorithm==
 It's a log2(N) algorithm where we recursively compare and swap elements 2 by 2 in a very specific manner.
@@ Line 25: / Line 26: @@
 [[File:BitonicBuild1.png]]
 ==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.
@@ Line 42: / Line 46: @@
 [[File:BitonicCompare2.png]]

← Older revision		Revision as of 13:58, 11 September 2015
Line 14:		Line 14:

	==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.
		+
		+	For 8 values, we first perform 4 compare&swaps like this:
		+
		+	[[File:BitonicBuild0.png]]
		+
		+	Then we perform 4 compares&swaps like this:
		+
		+	[[File:BitonicBuild1.png]]

← Older revision		Revision as of 13:48, 11 September 2015
Line 28:		Line 28:

	[[File:BitonicCompare1.png]]		[[File:BitonicCompare1.png]]
		+
		+	Finally we perform 4 compares&swaps like this:
		+
		+	[[File:BitonicCompare2.png]]

@@ Line 21: / Line 21: @@
 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]]

← Older revision		Revision as of 13:39, 11 September 2015
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]]

@@ Line 3: / Line 3: @@
 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)
+* 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.
+** For example:  (1, 2, 3, 4) followed by (4,3,2,1) is bitonic.
-** The bitonic sort algorithm works in 2 parts:
+* The bitonic sort algorithm works in 2 parts:
-*** '''(1)''' First, you need to transform any random sequence of numbers into a bitonic sequence
+** '''(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
+** '''(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.