挿入ソート

挿入ソートは手持ちのトランプを並び替えるときに使われる、自然で思いつきやすいアルゴリズムの1つである。片手に持ったトランプを左から小さい順に並び替える場合、1枚ずつカードを取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入していくことによって、カードを並び替えることができる。プログラム中の while (j >= 0 && A[j] > v) という部分は、「左側にずらしながら挿入場所を探す」作業をしている。

アルゴリズム

void InsertionSort(int A[], int N)
{
    for (int i = 0; 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;

        printArray(A, N);
    }
}

N個の要素を含む数列Aを昇順に並び替えるバブルソートのプログラムは以下のようになる。

#include <stdio.h>

void printArray(int A[], int N);

void InsertionSort(int A[], int N)
{
    for (int i = 0; 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;

        printArray(A, N);
    }
}

void printArray(int A[], int N)
{
    for (int i = 0; i < N; i++)
    {
        printf("%d", A[i]);
        if (i < N - 1)
        {
            printf(" ");
        }
    }
    printf("\n");
}

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

    InsertionSort(A, N);

    return 0;
}

挿入ソート

最新の記事・更新