CODEWITHSUNDEEP
c++algorithmrotation
Mircea Ispas
Mircea Ispas

Reputation: 20790

Demonstration for rotation algorithms

In many places I see array rotation for the range [begin, end) with "middle point" m implemented as:

void rotate(begin, m, end)
    reverse(begin, end);
    reverse(begin, m);
    reverse(m, end)

where reverse function is the equivalent of std::reverse and this works fine. The standard library algorithm std::rotate goes even further, making the rotation only with forward_iterators (reverse need bidirectional_iterators).

Do you know where I can find the formal demonstration for the rotation algorithms or can you please explain it to me here if there is a simple demonstration that can fit in SO answer?

Upvotes: 2

Views: 125

Answers (3)

Mircea Ispas
Mircea Ispas

Reputation: 20790

I've found a nice video about this on youtube. The rotation is better explained than it was in Elements of Programming where a dumb guy like me just didn't get it.

https://www.youtube.com/watch?v=7v3WRYLXjfI&index=11&list=PLHxtyCq_WDLW0NqZCcrrQUa24H_af6Mrn

Upvotes: 0

Paul Evans
Paul Evans

Reputation: 27577

Think about that axis point m:

begin----->m-1,m,m+1----->end-1

after reverse(begin, end):

end-1----->m+1,m,m-1----->begin

after reverse(begin, m):

m+1----->end-1,m,m-1----->begin

after reverse(m, end):

m+1----->end-1,begin----->m-1,m

thus rotating begin...m to the last places and rotating m+1...end-1 to the first places.

Upvotes: 2

IVlad
IVlad

Reputation: 43507

I'll try to offer a visual proof.

Consider a string like this:

begin----->m--->end

Applying reverse(begin, end) will result in:

begin<---m<-----end

Applying reverse(begin, m) will result in:

begin--->m<-----end

And finally reverse(m, end) will lead to:

begin--->m----->end

Thus rotating the string.

Upvotes: 2

Related Questions