ALDS1_1_A: Insertion Sort

AOJ AOJ本

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造（渡部有隆著，Ozy・秋葉拓哉協力）』を読んで解きました．

　

問題

　

ソースコード

#include <stdio.h>

//挿入ソート
void insertionSort(int A[], const int N)
{
    int i, j;

    for( i = 0; i < N; ++i ){
        int tmp = A[i];
        for( j = i-1; -1 < j && tmp < A[j]; --j ){
            A[j+1] = A[j];
        }
        A[j+1] = tmp;

        //出力
        for( j = 0; j < N; ++j ){
            printf("%d", A[j]);
            if( j != N-1 ) printf(" ");
        }
        printf("\n");
    }
}

int main()
{
    int i;

    //入力
    int N;
    scanf("%d", &N);
    int A[N];
    for( i = 0; i < N; ++i )
        scanf("%d", &A[i]);

    insertionSort(A, N);

    return 0;
}

　

反省点

  • 問題文に書かれているアルゴリズムのうち，while文をfor文に書き直す
  • 何も考えずにvをA[i]で置換してバグ
  • A[i]は即座に書き換えられていることに気付き，vを分かりやすくtmpに変えて適用
  • 入力のままが二回出力されている
  • mainで入力後に出力するのをやめる
  • 一発AC
  • 等差数列の和は 項数*(初項+末項)/2
  • 従って最悪時間計算量は (N-1)*(1+N-1)/2 = (N2-N)/2