３．２ 挿入ソート

本章では、冒頭の説明の中でアルゴリズムが文章で明示されてますので、それをそのまま実装してみます。

#include <iostream>
#include <array>

#include <cstdio>

void printArray(int A[], int N) {
  // カンニング１
  for (auto i = 0; i < N; i++) {
    std::cout << (i != 0 ? " " : "") << A[i];
  }
  std::cout << std::endl;
}

void insersionSort(int A[], int N) {
  int v, j;
  // カンニング２
  //  for (auto i = 1; i < N - 1; i++) {                                                                                                                              
  for (auto i = 1; i < N; i++) {
    v = A[i];
    j = i - 1;
    while (j >= 0 && A[j] > v) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    printArray(A, N);
  }
}

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

  std::array<int, 100> A;
  // カンニング１
  for (auto i = 0; i < N; i++) {
    scanf("%d", &A[i]);
  }

  printArray(A.data(), N);
  insersionSort(A.data(), N);
}

まず、「カンニング」というコメントについて解説？します。

• カンニング１
  • 空白区切りのデータを入出力する箇所です。仕事ではまずこんなコードは書かないのでカンニングしました。
• カンニング２
  • 本文の説明が「for i が 1 から N - 1 まで」となっていたため、単純に N - 1 をループ到達条件に入れていたら、思うような結果にならなかったので、条件どおり作ってるのになぜだろう？と悩んだところです。ちゃんと読めばそれはそうだろうという感じではありますが・・・

以下余談

• 自分は「using namespace std」があまり好きではないので、「std::」をきっちり書くのですが、若干めんどくさくなってきたため、これ以降は「using namespace std」を使うことにします。
• 関数の配列の引数表記として「int A[]」と書きましたが、もうちょっと粋な書き方がありそうです。
• cstdio と iostream を使いこなすことは競技プログラミングでは必須テクニックのように思えますね。色々なデータの入出力に慣れておかないと、調査の時間ばっかりかかってしまいます。