ALDS1_1_A: 挿入ソート

問題

• 挿入ソート | アルゴリズムとデータ構造 | Aizu Online Judge
• ソートに関する問題

解答

問題文に記載されている挿入ソートのアルゴリズムを実装します。出力は、ソート前に 回と、各計算ステップの途中経過を 回の、合計 回行います。

C++

#include <iostream>
using namespace std;

const int MAX_N = 100;

// 配列の要素を出力
void trace(int (&A)[MAX_N], int N) {
    for (int i = 0; i < N; ++i) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i];
    }
    cout << endl;
}

// 挿入ソート
void insertionSort(int (&A)[MAX_N], int N) {
    for (int i = 1; i < N; ++i) {
        int v = A[i];
        int j = i - 1;
        while (j >= 0 && A[j] > v) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = v;
        trace(A, N);
    }
}

int main() {
    int N;
    int A[MAX_N];

    // 入力
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // 配列の要素を出力
    trace(A, N);

    // 挿入ソート
    insertionSort(A, N);

    return 0;
}

Python

# coding: utf-8

N = int(input())
A = list(map(int, input().split()))

print(*A)

for i in range(1, len(A)):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j + 1] = A[j]
        j -= 1
    A[j + 1] = v
    print(*A)