配列の左回転の実装比較

rotation.cpp

#include <iostream>
#include <vector>
#include <random>

// shift array left 1 time
int shiftLeft(std::vector<int>& ary) {
  using std::vector;
  if(ary.size() > 2) {
    int t = ary[0];
    for(int i=1; i<ary.size(); i++){
      ary[i-1] = ary[i]; 
    }
    ary[ary.size()-1] = t;
  }
  return 0;
}
// shift array left N times
int leftRotation(std::vector<int>& ary, int N=1) {
  for(int i=0;i<N;i++) shiftLeft(ary);
  return 0;
}

// 
int leftRotationSkip(std::vector<int>& ary, int N=1){
  long count = 0;
  for(int j=0;count<ary.size();j++) {//すべて移動するまで
    int t = ary[j];
    for(int i=j;i<ary.size();i++){
      int prev = (N*(i-1)+j)%ary.size();
      int next = (N*i+j)%ary.size();
      if(next == 0) {
        ary[prev] = t;
        break;
      } else {
        ary[prev] = ary[next];
      }
      // 動かした要素数を計数
      count++;
    }
  }
  return 0;
}

void showData(const std::vector<int>& ary){
  for(int i=0;i<ary.size();i++)
    std::cout<<ary[i]<<" ";
  std::cout<<std::endl;
}

int main(void) {
  using std::vector;
  const long N = 1e5;
  const long seed = 100;
  vector<int> ary(N);
  std::mt19937 mt(seed);
  for(int i=0;i<N;i++) {
    //ary[i] = mt()%N;
    ary[i] = i+1;
  }
  //showData(ary);//before
  const auto startTime = std::chrono::system_clock::now();
  leftRotation(ary, N);
  //leftRotationSkip(ary, N);
  const auto endTime = std::chrono::system_clock::now();
  const auto timeSpan = endTime - startTime;
  //showData(ary);//after
  std::cout << "time:" << std::chrono::duration_cast<std::chrono::milliseconds>(timeSpan).count() << "[ms]" << std::endl;
  return 0;
}