アルゴリズム

単純挿入ソート

更新日:

単純挿入ソートとは

単純挿入ソートのアルゴリズムについて解説します。

一番端から順番に既にソートされているものとし、次の値をソートされている列の所定の位置に挿入していきます。

以下の配列を例に挙げ、実際にみていきましょう。

添え字 [0] [1] [2] [3] [4]
4 2 9 6 0

0番目の4を既にソートされているものとし、次の2をソート済みの列の後ろから順に比較していきます。
一番後ろの4より小さいので並べ変えます。

添え字 [0] [1] [2] [3] [4]
2 4 9 6 0

次に9を比較すると4より大きいので位置は変わりません。

添え字 [0] [1] [2] [3] [4]
2 4 9 6 0

以下同様に入れ替えていきます。

添え字 [0] [1] [2] [3] [4]
2 4 6 9 0
添え字 [0] [1] [2] [3] [4]
2 4 6 9 0
添え字 [0] [1] [2] [3] [4]
2 4 6 0 9
添え字 [0] [1] [2] [3] [4]
2 4 0 6 9
添え字 [0] [1] [2] [3] [4]
2 0 4 6 9
添え字 [0] [1] [2] [3] [4]
0 2 4 6 9

これでソートは完了です。

ソースコード

以下がソースコードです。

insertsort_sample.c

#include <stdio.h>

void show_array(int a[], int len)
{
	int i;
	for (i = 0; i < len; i++)
		printf("%d ", a[i]);

	printf("\n");
}

int main(void)
{
	int arr[] = { 5, 2, 6, 1, 3, 9 , 3, 7, 4, 0};
	int arr_len = 10;	//配列の長さ
	int i, j, temp;

	for (i = 1; i < arr_len; i++)
	{
		temp = arr[i];
		for (j = i; j > 0 && arr[j - 1] > temp; j--)
			arr[j] = arr[j - 1];

		arr[j] = temp;

		show_array(arr, arr_len);
	}

	return 0;
}

このコードでは挿入する値をtempに保存しておき、arr[j]が挿入する値よりも大きければ一つずつ位置をずらしています。
その後、所定の位置までずらしたら空いたところにtempを挿入しています。



-アルゴリズム

Copyright© ツナのエンジニアブログ , 2024 All Rights Reserved Powered by AFFINGER5.