兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

3.3 バブルソート

まずは冒頭の説明をそのままコーディングします。

#include <iostream>
#include <array>

#include <cstdio>

using namespace std;

static void printArray(int A[], int N) {
  for (auto i = 0; i < N; i++) {
    cout << (i != 0 ? " " : "") << A[i];
  }
  cout << endl;
}

static int bubbleSort(int A[], int N) {
  bool flag = true;
  int count = 0, tmp;
  while (flag) {
    flag = false;
    for (auto j = N - 1; j > 0; j--) {
      if (A[j] < A[j - 1]) {
        tmp = A[j - 1];
        A[j - 1] = A[j];
        A[j] = tmp;
        flag = true;
        count++;
      }
    }
  }
  return count;
}

int main() {
  int N;
  cin >> N;

  array<int, 100> A;
  for (auto i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }

  auto count = bubbleSort(A.data(), N);
  printArray(A.data(), N);
  cout << count << endl;

  return 0;
}

文字列の入出力は前回の関数が使えるので楽ですね。

閑話休題c++11 なので、所々に auto を使ってますが、int って素直に書いたほうがタイピング数が減ることに気づきました。まあ auto が好きなのでこのままとします。

後半の説明の変数 i を導入すると、bubbleSort() は、

static int bubbleSort(int A[], int N) {
  bool flag = true;
  int count = 0, tmp;
  int i = 0;
  while (flag) {
    flag = false;
    for (auto j = N - 1; j > i; j--) {
      if (A[j] < A[j - 1]) {
        tmp = A[j - 1];
        A[j - 1] = A[j];
        A[j] = tmp;
        flag = true;
        count++;
      }
    }
    i++;
  }
  return count;
}

となりました。書籍内の回答例では、i と flag を for にまとめてたり、swap() 関数を使ってましたね。なるほどと思いました。