[Bitonic Sort] what is rotation ? and is there any formal algorithm for it ?

[doduythao]

I don't understand the definition of rotation in the lecture. Also is there any formal algorithm for bitonic merge func ? (like the formal in odd-even merge). Any one can help ? Thank in advance my savior

[CauchyComplete]

1. S' is said to be a rotation of S if there exists an integer k such that S'[i+k]==S[i] for all i. Note that I'm denoting S[i+2n]==S[i] where S has length of 2n.

2. pseudocode for bitonic merge
   def bitonicMerge(comparision operator <, sequence X) :
   if |X| == 1 then return X
   A = xchgL(X)
   B = xchgR(X)
   A' = bitonicMerge(<,A) # recursion
   B' = bitonicMerge(<,B) # recursion
   X' = A' ++ B' # concatenation
   return X'

[doduythao]

@CauchyComplete I think it should be for each i, there is one k for each i, right ? e.g. for: i=1 k could be 5, i=2 k could be another number.
right ? not all i in S using the same k ?

[HaritzPuerto]

@doduythao Maybe an example would clarify it. As I understood from the class, given this sequence <1,2,3,4> a rotation would be <2,3,4,1> and of course there are more rotations like <3,4,1,2>
Hope it helps, and please, let me know if I am wrong :)

[LLJE]

@CauchyComplete I followed your pseudocode, but I got wrong result.
Did I follow wrong way?

[ppnchb]

@LLJE Bitonic merge needs bitonic sequence as an input, and outputs a sorted sequence

[LLJE]

@ppnchb Ah, I see. I confused it with bitonic sort. Thanks.

[CauchyComplete]

@doduythao It's one k all i, not k_i for each i.

[jeehoonkang]

@doduythao I believe the discussion here answers your question, right?

[doduythao]

Thanks. I know got the "Note that I'm denoting S[i+2n]==S[i] where S has length of 2n."