単純挿入法(Insertion Sort)
Top -> プログラミング -> アルゴリズム(Algorithm by the C language) -> 単純挿入法(Insertion Sort)
1.単純挿入法(Insertion Sort)とは

このソートアルゴリズムは、ソート済みの集合体の中からソートする値を適切な位置に挿入していくアルゴリズムです。ちょうど、トランプの手札を並べ替えるような感じでソートされます。

単純挿入法(Insertion Sort)は安定しているソートアルゴリズムです。

2.単純挿入法(Insertion Sort)の実装
  1. 集合体の2番目の値の場所から最後まで、以下を繰り返す。先頭はソート済みとみなす。
  2. 決定項の初期値を、現在のソート対象位置の値を代入する。
  3. ソート済みの集合体の中から、入れるべき場所を探し、場所を空ける。
  4. 空けた場所に決定項を代入する。

*ptrはint型変数の配列への先頭ポインタ、nはデータの個数です。

void insertion_sort(int *ptr, int n) { int i, j, k; for(i=1; i<n; i++){ k = *(ptr+i); for(j = i-1; j >=0 && k<*(ptr+j); j--){ *(ptr+j+1) = *(ptr+j); } *(ptr+j+1) = k; } }

また

for(j = i-1; j >=0 && k<*(ptr+j); j--){

for(j = i-1; j >=0 && k>*(ptr+j); j--)

のように、判定条件を変更すると降順になります。今回のサンプルソースは昇順です。

サンプル

以下のリンクからサンプルを閲覧又はダウンロードできます。
このサンプルはSHIFT-JISで書かれております。

閲覧またはダウンロード
戻る
カウンター