第11章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って， そこで作業することを前提とする．作成していない時は，ターミナルから 
mkdir ~/mis2
を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は， 
cd ~/mis2
tar zxvf ods-cpp.tgz
ods-cpp.tarというファイルができた時は， 
cd ~/mis2
tar xvf ods-cpp.tar
を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]クイックソート(QuickSort)を使ったことがある?

  1. ライブラリとしては使ったことがある．
  2. 自分でプログラムを書いたことがある．
  3. 1，2の両方が当てはまる．
  4. 1，2の両方共当てはまらない．あるいは，QuickSortという言葉を初めて聞いた．

[投票]ヒープソート(HeapSort)を使ったことがある?

  1. ライブラリとしては使ったことがある．
  2. 自分でプログラムを書いたことがある．
  3. 1，2の両方が当てはまる．
  4. 1，2の両方共当てはまらない．あるいは，ヒープソートという言葉を初めて聞いた．

[投票]マージソート(MergeSort)を使ったことがある?

  1. ライブラリとしては使ったことがある．
  2. 自分でプログラムを書いたことがある(情報科学の講義でプログラムを完成させたものも含む)．
  3. 1，2の両方が当てはまる．
  4. 1，2の両方共当てはまらない．あるいは，マージソートという言葉を初めて聞いた

[投票]基数ソート(Radix Sort)を使ったことがある?

  1. ライブラリとしては使ったことがある．
  2. 自分でプログラムを書いたことがある．
  3. 1，2の両方が当てはまる．
  4. 1，2の両方共当てはまらない．あるいは，Radix Sortという言葉を初めて聞いた．

演習(Sorting)

~/mis2/cpp 以下にsortTest.cpp というファイルを作成する． 
#include "array.h"
using namespace ods;
#include "ArrayStack.h"
#include "BinaryHeap.h"
#include "Algorithms.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

int main(){
  std::vector<int> v(1000000);
  for (int i = 0; i < 1000000; i++) v[i] = rand() % 100;
  for (int n = 1000; n <= 1000000; n *= 10){
    array<int> a(n);
    for (int i = 0; i < n; i++) a[i] = v[i];
    clock_t start, stop;
    {
      start = clock();
      mergeSort(a);
      stop = clock();
      std::cout << "mergeSort(size = " << n << ") : " << ((double)(stop-start))/CLOCKS_PER_SEC << " sec" << std::endl;
    }
    {
      start = clock();
      quickSort(a);
      stop = clock();
      std::cout << "quickSort(size = " << n << ") : " << ((double)(stop-start))/CLOCKS_PER_SEC << " sec" << std::endl;
    }
    {
      start = clock();
      heapSort(a);
      stop = clock();
      std::cout << "heapSort(size = " << n << ") : " << ((double)(stop-start))/CLOCKS_PER_SEC << " sec" << std::endl;
    }
    {
      start = clock();
      countingSort(a, 100);
      stop = clock();
      std::cout << "countingSort(size = " << n << ") : " << ((double)(stop-start))/CLOCKS_PER_SEC << " sec" << std::endl;
    }
    {
      start = clock();
      radixSort(a);
      stop = clock();
      std::cout << "radixSort(size = " << n << ") : " << ((double)(stop-start))/CLOCKS_PER_SEC << " sec" << std::endl;
    }
  }
}
これを， 
cd ~/mis2/cpp
g++-5 -O3 -Wall  -o sortTest sortTest.cpp
でコンパイルし， 
./sortTest
で実行する．