1

I am rotating an array or vector clockwise and counterclockwise in C++. Which is the most efficient way in terms of time complexity to do that ? I used rotate() function but I want to know is there any faster methods than this ?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   vector<int> v;
   for(int i=0;i<5;i++)
      v.push_back(i);
   int d=2;
   rotate(v.begin(),v.begin()+d,v.end());
   return 0;
}
Vaishal
  • 187
  • 1
  • 3
  • 15

3 Answers3

3

rotate() is a linear time function and that is the best you can do.

However, if you need to do multiple rotates, you can accumulate.

For eg: rotation of 4 and rotation of 5 is same as a single rotate of 9.

Or in fact, in some applications, you may not even want to actually rotate.

Like, if you want to rotate by 'd'. You can just make a function that returns v[(i+d)%v.size()] when asked for v[i]. This is constant time solution. But like I said, this is application specific.

knsn1994
  • 136
  • 4
2

General answer for the "can I make XY faster?" kind of question: Maybe you can. But probably you shouldn't.

std::rotate is designed to be efficient for the average case. That means, if you have a very specific case, it might be possible to have a more performant implementation for that case.

BUT:

  • Don't bother to search for a more performant implementation for your specific case, because finding that specific implementation will require you to know about the detailed performance of the steps you take and about the optimizations your compiler will perform.
  • Don't bother to implement it, because you will have to test it and still your coverage of corner cases won't be as good as the tests already performed with the standard library implementation.
  • Don't use it, because someone will be irritaded, asking himself by why you rolled your own implementation and not just used the standard library. And someone else will use it for a case where it is not as performant as the standard implementation.
  • Don't invest time to improve the performance of a clear piece of code, unless you are 100% sure that it is a performance bottleneck. 100% sure means, you have used a profiler and pinpointed the exact location of the bottleneck.
Community
  • 1
  • 1
Arne Mertz
  • 24,171
  • 3
  • 51
  • 90
0
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

    void rotatebyone(int arr[], int n) {
    int temp= arr[0], i;
    for(i=0;i<n;i++)
    {
      arr[i]=arr[i+1];
      arr[n]=temp;
    }
  }

int main()
{
    int arr[]={2,3,4,5,6,7,8};
    int m= sizeof(arr)/sizeof(arr[0]);
    int i;
    int d=1;

    for(i=0;i<d;i++) {          //function to implement it d no of times
        rotatebyone(arr,m);
    }

    for(i=0;i<m;i++) {
        cout<<arr[i]<<"";
    }

return 0;
}
Nan artz
  • 1
  • 1
  • The code has a complexity of O(n*d) and space complexity O(1). There are 1-2 more approaches that can reduce the complexity to O(n). – Nan artz Aug 10 '21 at 13:41
  • Welcome to Stack Overflow! Thank you for reading our Tour. Please see [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) and [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – IWonderWhatThisAPIDoes Aug 10 '21 at 13:53