LoginSignup
0

More than 3 years have passed since last update.

C言語 ALDS1_1_A Insertion Sort

Last updated at Posted at 2020-04-03

問題

コード

#include <stdio.h>

static void print_array(int array[], int array_len)
{
    for (int i = 0; i < array_len; i++)
    {
        printf("%d", array[i]);
        if (i != array_len - 1)
            printf(" ");
    }
    printf("\n");
}

static void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void)
{
    int N;
    int A[100];

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

    /* 出力 */
    print_array(A, N);

    /* 挿入ソート */
    for (int i = 1; i < N; i++)
    {
        for (int j = i - 1; j >= 0; j--)
            if (A[j] > A[j + 1])
                swap(&A[j], &A[j + 1]);
        print_array(A, N);
    }
    return 0;
}

所感

  • 配列は「ソート済みの部分列」と「未ソートの部分列」とに分けられる。
  • int j = i - 1で、ソート済みのところを計算しないようにする。
  • 比べるのは、常に隣り合う数

所要時間50分

【復習】

  • 2020/04/05
    • ソート済み配列へのj--で下がっていくイメージを持ててなかった

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0