3

The ELEMENTS が 25 である代わりに、要素の大きな配列をランダムに生成する方法があります.... 10000、100000、または 1000000 要素であり、挿入ソート アルゴリズムを使用します。私は要素の大きな配列を持ち、挿入ソートを使用してそれらを並べ替え、次に逆順に並べようとしています。次に、time.h ファイルで clock() を使用して、各アルゴリズムの実行時間を計算しました。大量の数字でテストしようとしています。 

#define ELEMENTS 25

void insertion_sort(int x[],int length);
void insertion_sort_reverse(int x[],int length);

int main()
{
  clock_t tStart = clock();
  int B[ELEMENTS]={4,2,5,6,1,3,17,14,67,45,32,66,88,
               78,69,92,93,21,25,23,71,61,59,60,30};
  int x;

  cout<<"Not Sorted: "<<endl;
  for(x=0;x<ELEMENTS;x++)
       cout<<B[x]<<endl;

   insertion_sort(B,ELEMENTS);
   cout <<"Sorted Normal: "<<endl;
  for(x=0;x<ELEMENTS;x++)
       cout<< B[x] <<endl;

  insertion_sort_reverse(B,ELEMENTS);
  cout <<"Sorted Reverse: "<<endl;
  for(x=0;x<ELEMENTS;x++)
       cout<< B[x] <<endl;

  double seconds = clock() / double(CLK_TCK);
  cout << "This program has been running for " << seconds << " seconds." << endl;
  system("pause");
  return 0;
}
4

3 に答える 3

18 
#include <random>     // mt19937 and uniform_int_distribution
#include <algorithm>  // generate
#include <vector>     // vector
#include <iterator>   // begin, end, and ostream_iterator
#include <functional> // bind
#include <iostream>   // cout

std::vector<int> create_random_data(int n) {
  std::random_device r;
  std::seed_seq      seed{r(), r(), r(), r(), r(), r(), r(), r()};
  std::mt19937       eng(seed); // a source of random data

  std::uniform_int_distribution<int> dist;
  std::vector<int> v(n);

  generate(begin(v), end(v), bind(dist, eng));
  return v;
}

int main() {
  auto random_data = create_random_data(100000);

  std::cout << "unsorted: ";
  copy(begin(random_data), end(random_data),
       std::ostream_iterator<int>(std::cout, "\n"));
}

generateファンクターによって生成された値で範囲を埋める汎用アルゴリズムです。この場合、乱数データのソースを使用して乱数を生成するファンクタを提供し、コンテナに対応する範囲を提供します。これは、コンテナにgenerateデータを入力した後に使用できます。

std::mt19937C++11 (およびVS2010で利用可能) の標準 C++ 機能である and を使用して、古い方法std::uniform_int_distributionの代わりに乱数を作成します。新しい方法は、正しく使用しやすく、品質が高く、柔軟性が高いためです。std::rand()std::srand()

VS2012 以降を使用している場合は、C++11 時間ライブラリを利用できます。

#include <chrono>

int main() {
  using std::chrono::high_resolution_clock;
  using std::chrono::duration_cast;
  using std::chrono::nanoseconds;

  auto start = high_resolution_clock::now();

  // ...

  auto end = high_resolution_clock::now();

  std::cout << duration_cast<nanoseconds>(end - start).count() << "ns\n";
}
于 2012-08-27T21:09:43.930 に答える
4

それ以外の

void insertion_sort(int x[],int length);
void insertion_sort_reverse(int x[],int length);

 int B[ELEMENTS]={4,2,5,6,1,3,17,14,67,45,32,66,88,
           78,69,92,93,21,25,23,71,61,59,60,30};

試す

void insertion_sort(std::vector<int>& x);
void insertion_sort_reverse(std::vector<int>& x);

 srand(NULL);
 std::vector<int> B(num_elements); //num_elements can be a variable
 std::generate(B.begin(), B.end(), rand);

質問ではなくタスクに関連して:
各ソートを 2 回続けて実行する必要があります。1 回目はタイミングなし、2 回目はタイミングありです。
一方はランダムな位置から開始し、もう一方はソートされた位置から開始するため、テストは公平ではありません。
IO をタイミングに含めており、IO は常に遅い ( cout)
std::endlは、プログラムがすべての出力をすぐに OS に渡すように強制します'\n'。
まったく関係のない秒数を表示しています。 

int main()
{
  srand(NULL);
  std::vector<int> B(num_elements); //num_elements can be a variable
  std::generate(B.begin(), B.end(), rand);
  std::vector<int> C(B); //make a copy of the data

  std::cout << "Not Sorted:" << '\n';
  for(int i=0;i<B.size();i++)
       cout<<B[i]<<'\n';

  clock_t tStart0 = clock();        
  insertion_sort(B,ELEMENTS);
  clock_t tStop0 = clock();     

  cout <<"Sorted Normal: "<<'\n';
  for(int i=0;i<B.size();i++)
       cout<< B[i] <<'\n';

  clock_t tStart1 = clock();        
  insertion_sort_reverse(C);
  clock_t tStop1 = clock();  

  cout <<"Sorted Reverse: "<<'\n';
  for(int i=0;i<C.size();i++)
       cout<< C[i] <<'\n';

  double seconds = (tStop1-tStart1 + tStop0-tStart0) / double(CLK_TCK);
  cout << "This program has been running for " << seconds << " seconds." << endl;
  system("pause");
  return 0;
}
于 2012-08-27T21:10:46.153 に答える