verify/local/bubble-sort-test.cpp

• View this file on GitHub
• Last update: 2025-06-18 01:09:16+09:00

Depends on

• バブルソート (sort/bubble-sort.hpp)
• template.hpp

Code

#include "../../template.hpp"
#include "../../sort/bubble-sort.hpp"

// テスト用関数 - 配列がソートされているかチェック
template <class T>
bool isSorted(const vector<T>& arr) {
  for (size_t i = 1; i < arr.size(); ++i) {
    if (arr[i-1] > arr[i]) return false;
  }
  return true;
}

// テスト実行用関数
template <class T>
bool runSortTest(const string& testName, vector<T> arr, const vector<T>& expected) {
  cout << "テスト " << testName << ": ";

  // 元の配列を表示
  cout << "\n  入力: [";
  for (size_t i = 0; i < arr.size(); ++i) {
    if (i > 0) cout << ", ";
    cout << arr[i];
  }
  cout << "]" << endl;

  // バブルソート実行
  int swapCount = bubbleSort(arr, true);

  // ソート結果を表示
  cout << "  出力: [";
  for (size_t i = 0; i < arr.size(); ++i) {
    if (i > 0) cout << ", ";
    cout << arr[i];
  }
  cout << "]" << endl;
  cout << "  交換回数: " << swapCount << endl;

  // 結果の検証
  bool correctSort = isSorted(arr);
  bool matchesExpected = (arr == expected);

  if (correctSort && matchesExpected) {
    cout << "  結果: 成功 ✓" << endl;
    return true;
  } else {
    cout << "  結果: 失敗 ✗" << endl;
    if (!correctSort) {
      cout << "    エラー: 配列が正しくソートされていません" << endl;
    }
    if (!matchesExpected) {
      cout << "    エラー: 期待結果と一致しません" << endl;
      cout << "    期待結果: [";
      for (size_t i = 0; i < expected.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << expected[i];
      }
      cout << "]" << endl;
    }
    return false;
  }
}

// すべてのテストを実行
void runAllTests() {
  int passedCount = 0;
  int totalTests = 0;

  // テストケース1: 標準的な配列
  {
    vector<int> arr = {5, 3, 8, 1, 2, 7, 4, 6};
    vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8};
    if (runSortTest("ケース1 (標準的な配列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース2: 既にソート済みの配列
  {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> expected = {1, 2, 3, 4, 5};
    if (runSortTest("ケース2 (ソート済み)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース3: 逆順の配列
  {
    vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    if (runSortTest("ケース3 (逆順)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース4: 重複を含む配列
  {
    vector<int> arr = {4, 2, 4, 1, 3, 2};
    vector<int> expected = {1, 2, 2, 3, 4, 4};
    if (runSortTest("ケース4 (重複あり)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース5: 単一要素
  {
    vector<int> arr = {42};
    vector<int> expected = {42};
    if (runSortTest("ケース5 (単一要素)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース6: 空配列
  {
    vector<int> arr = {};
    vector<int> expected = {};
    if (runSortTest("ケース6 (空配列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース7: 浮動小数点数
  {
    vector<double> arr = {3.14, 1.41, 2.71, 1.73};
    vector<double> expected = {1.41, 1.73, 2.71, 3.14};
    if (runSortTest("ケース7 (浮動小数点数)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース8: 文字列
  {
    vector<string> arr = {"orange", "apple", "banana", "grape"};
    vector<string> expected = {"apple", "banana", "grape", "orange"};
    if (runSortTest("ケース8 (文字列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // 結果を表示
  cout << "\n全" << totalTests << "テスト中 " << passedCount << "個成功 (" 
       << (passedCount * 100 / totalTests) << "%)" << endl;
}

int main() {
  cout << "=== バブルソート自動テスト ===" << endl;
  runAllTests();
  return 0;
}

#line 1 "template.hpp"
#include<bits/stdc++.h>
using ll = long long;
#define REP(i, n) for(ll i = 0; (i) < ll(n); ++ (i))
#define FOR(i, m, n) for(ll i = (m); (i) <= ll(n); ++ (i))
#define REPR(i, n) for(ll i = ll(n) - 1; (i) >= 0; -- (i))
#define FORR(i, m, n) for(ll i = ll(n); (i) >= ll(m); -- (i))
#define ALL(x) x.begin(),x.end()

#define INF (int)1e9
#define LLINF (long long)1e18
#define MOD (int)(1e9+7)
#define MOD9 (int)998244353
#define PI 3.141592653589
#define PB push_back
#define F first
#define S second

#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Yes(T) {cout<<"Yes"<<endl; if(T) return 0;}
#define No(T) {cout <<"No"<<endl; if(T) return 0;}
#define YES(T) {cout<<"YES"<<endl; if(T) return 0;}
#define NO(T) {cout <<"NO"<<endl; if(T) return 0;}

#define Graph vector<vector<int> >
#define CostGraph vector<vector<pair<int,ll> > >
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define VI vector<int>
#define VL vector<ll>
#define VVI vector<vector<int> >
#define VVL vector<vector<ll> >
#define VPII vector<pair<int,int> >
#define VPLL vector<pair<ll,ll> >

#define DDD fixed<<setprecision(10)
#define PAD setfill('0')<<right<<setw(8)

template <class T>
inline bool chmin(T &a, T b) {
  if(a > b){ a = b; return true;}
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if(a < b){a = b; return true;}
  return false;
}
struct input{
  int n;
  input() {}
  input(int n_) : n(n_){};
  template <class T>
  operator T(){
    T ret;
    std::cin >> ret;
    return ret;
  }
  template <class T>
  operator std::vector<T>() {
    std::vector<T> ret(n);
    REP(i,n) std::cin >> ret[i];
    return ret;
  }
};
template <class T>
inline void printVec(std::vector<T> v){
  REP(i,v.size()){
    if(i) std::cout << " ";
    std::cout << v[i];
  } std::cout << std::endl;
}

using namespace std;
#line 2 "sort/bubble-sort.hpp"

/**
 * @brief バブルソート - O(n^2)の比較ベースソートアルゴリズム
 * @tparam T 配列の要素の型
 * @param[in,out] arr ソートする配列
 * @param[in] verbose 詳細表示フラグ（デフォルトはfalse）
 * @return int 交換回数
 */
template <class T>
int bubbleSort(vector<T>& arr, bool verbose = false) {
  int n = arr.size();
  int swapCount = 0;

  for (int i = 0; i < n - 1; ++i) {
    bool swapped = false;

    // 各パスで最大値を右端に移動（降順に処理）
    for (int j = 0; j < n - 1 - i; ++j) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
        swapCount++;
        swapped = true;
      }
    }

    // 途中で交換が発生しなければ既にソート済み
    if (!swapped) break;

    // 詳細表示モード
    if (verbose) {
      cout << "Pass " << (i + 1) << ": ";
      for (int k = 0; k < n; ++k) {
        if (k > 0) cout << " ";
        cout << arr[k];
      }
      cout << endl;
    }
  }

  return swapCount;
}
#line 3 "verify/local/bubble-sort-test.cpp"

// テスト用関数 - 配列がソートされているかチェック
template <class T>
bool isSorted(const vector<T>& arr) {
  for (size_t i = 1; i < arr.size(); ++i) {
    if (arr[i-1] > arr[i]) return false;
  }
  return true;
}

// テスト実行用関数
template <class T>
bool runSortTest(const string& testName, vector<T> arr, const vector<T>& expected) {
  cout << "テスト " << testName << ": ";

  // 元の配列を表示
  cout << "\n  入力: [";
  for (size_t i = 0; i < arr.size(); ++i) {
    if (i > 0) cout << ", ";
    cout << arr[i];
  }
  cout << "]" << endl;

  // バブルソート実行
  int swapCount = bubbleSort(arr, true);

  // ソート結果を表示
  cout << "  出力: [";
  for (size_t i = 0; i < arr.size(); ++i) {
    if (i > 0) cout << ", ";
    cout << arr[i];
  }
  cout << "]" << endl;
  cout << "  交換回数: " << swapCount << endl;

  // 結果の検証
  bool correctSort = isSorted(arr);
  bool matchesExpected = (arr == expected);

  if (correctSort && matchesExpected) {
    cout << "  結果: 成功 ✓" << endl;
    return true;
  } else {
    cout << "  結果: 失敗 ✗" << endl;
    if (!correctSort) {
      cout << "    エラー: 配列が正しくソートされていません" << endl;
    }
    if (!matchesExpected) {
      cout << "    エラー: 期待結果と一致しません" << endl;
      cout << "    期待結果: [";
      for (size_t i = 0; i < expected.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << expected[i];
      }
      cout << "]" << endl;
    }
    return false;
  }
}

// すべてのテストを実行
void runAllTests() {
  int passedCount = 0;
  int totalTests = 0;

  // テストケース1: 標準的な配列
  {
    vector<int> arr = {5, 3, 8, 1, 2, 7, 4, 6};
    vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8};
    if (runSortTest("ケース1 (標準的な配列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース2: 既にソート済みの配列
  {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> expected = {1, 2, 3, 4, 5};
    if (runSortTest("ケース2 (ソート済み)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース3: 逆順の配列
  {
    vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    vector<int> expected = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    if (runSortTest("ケース3 (逆順)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース4: 重複を含む配列
  {
    vector<int> arr = {4, 2, 4, 1, 3, 2};
    vector<int> expected = {1, 2, 2, 3, 4, 4};
    if (runSortTest("ケース4 (重複あり)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース5: 単一要素
  {
    vector<int> arr = {42};
    vector<int> expected = {42};
    if (runSortTest("ケース5 (単一要素)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース6: 空配列
  {
    vector<int> arr = {};
    vector<int> expected = {};
    if (runSortTest("ケース6 (空配列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース7: 浮動小数点数
  {
    vector<double> arr = {3.14, 1.41, 2.71, 1.73};
    vector<double> expected = {1.41, 1.73, 2.71, 3.14};
    if (runSortTest("ケース7 (浮動小数点数)", arr, expected)) passedCount++;
    totalTests++;
  }

  // テストケース8: 文字列
  {
    vector<string> arr = {"orange", "apple", "banana", "grape"};
    vector<string> expected = {"apple", "banana", "grape", "orange"};
    if (runSortTest("ケース8 (文字列)", arr, expected)) passedCount++;
    totalTests++;
  }

  // 結果を表示
  cout << "\n全" << totalTests << "テスト中 " << passedCount << "個成功 (" 
       << (passedCount * 100 / totalTests) << "%)" << endl;
}

int main() {
  cout << "=== バブルソート自動テスト ===" << endl;
  runAllTests();
  return 0;
}

Back to top page