實作泡沫排序,並紀錄次數。
Implement bubble sorting and log the swap count.

UVa Link

#include <iostream>
#include <cstdio>

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);
  int t;
  std::cin >> t;
  while (t--) {
    int n, arr[100], swap = 0;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
      std::cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
      int jTimes = n - i - 1;
      for (int j = 0; j < jTimes; j++) {
        if (arr[j] > arr[j + 1]) {
          int tmp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = tmp;
          swap++;
        }
      }
    }
    std::cout << "Optimal train swapping takes " << swap << " swaps.\n";
  }
}