第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
で実行する.