プログラムの勉強のための問題集 - 問題９．配列のデータをソートしなさい（３） - 単純挿入法

問：記の配列のデータを単純挿入法を用いて昇順にソートしなさい。

#include <stdio.h>

int main(){
	int array[] = { 7, 3, 9, 2, 10, 8, 6, 5, 4, 1 };
	
	ここにソートプログラムを書く

	for(int i=0; i<10; i++){
		printf( "%3d", array[i] );
	}
	
	return 0;
}

■単純交換法とは？■
ソートの手法の一つで、

たとえば、下記のような数列があるとする。

②⑧③①⑤

これを昇順にソートしたいとすれば、

ここから一つずつ数字を取っていって、

既に取った数字の数列のどこに挿入すればいいのかを考えるようにする。

例を挙げればこのような感じ。

ソート後配列：②

ソート前配列：⑧③①⑤

まずは、②を取ってきて、ソート後配列に挿入する。

ソート後配列：②⑧

ソート前配列：③①⑤

次に⑧を取ってくる。②よりも⑧は大きいので、

②の後ろに挿入する。

ソート後配列：②③⑧

ソート前配列：①⑤

次に③を取ってくる。②より大きく、⑧より小さいので、②と⑧の間に挿入する。

ソート後配列：①②③⑧

ソート前配列：⑤

次に①を取ってくる。①は②より小さいので、②の前に挿入する。

ソート後配列：①②③⑤⑧

ソート前配列：

最後に⑤を取ってくる。⑤は③より大きく、⑧より小さいので、③と⑧の間に挿入する。

このようにすることで、ソートすることが出来るのです。　これが単純挿入法の考え方です。

解答と解説

このページのトップはこちら です。