3.1 単純挿入法
- 3.1.1 shellソート

3 C言語の練習

ソーティングとは、整列あるいは並び替えのことである²。プログラミングでは、数値を大きい順、あるいは小さい順に並び替える技法のことを言う。数値の並び替えは非常に重要な技法で、実際のプログラムではいたるところで使われいる。ソーティングでもっと重要なことは、処理速度である。高速な処理を目指していろいろなアルゴリズムが考えられている。ここでは、ソーティングの簡単なアルゴリズムを示し、C言語のプログラムの学習を進める。

3.1 単純挿入法

ソーティングの中でも、最も簡単な単純挿入法のプログラムを作成する。有名なC言語の本「NUMERICAL RECIPES in C」によると、これは経験を積んだトランプ師が使う方法と同じであるということである。順序がバラバラのトランプを並び替える場合、

まず、2枚目のカードを拾い、1枚目と順序関係が正しい位置に置く。
次に3枚目のカードを拾い、最初の2枚と順序関係の正しい位置にそれを挿入する。
同じことを繰り返す。即ち、枚目のカードを拾い、最初の枚のカードの順序関係の正しい位置にそれを挿入する。
　最後のカードを正しい位置に挿入したら、並び替えは完了である。

この単純挿入法を用いて、リスト1で作成された整数の配列 a[0]～a[1023]を小さい順に並び替えよ。このリストの19行目以降に単純挿入法のプログラムを書く。ヒント図1に単純挿入法のフローチャートを示す。

**図 1:** 単純挿入法のフローチャート。`ndata`はデータ数で、`a[0]～ a[nadata-1]`の配列に格納されている整数を小さい順(昇順)に並べる。
$\includegraphics[keepaspectratio, scale=1.0]{figure/flow_simple_sort.eps}$

   1 #include <stdio.h>
   2 #include <stdlib.h>    /* 乱数発生のため      */
   3 #include <time.h>      /* 時刻の関数を使うため */
   4 
   5 int main(void){
   6   int a[1024], i, j, ndata, test;
   7 
   8   ndata=1024;
   9 
  10   srand((unsigned int)time(NULL));    /* 起動毎に異なる乱数を発生させるため */
  11 
  12   for(i=0; i<ndata; i++){
  13     a[i]=rand();                      /* 配列a[i]に乱数の整数を設定 */
  14   }
  15 
  16 
  17 
  18   /*  これ以降に単純ソートと昇順に並んだ出力のプログラムを書く */
  19 
  20 
  21 
  22 
  23 
  24 
  25 
  26 
  27   return 0;
  28 }

3.1.1 shellソート

Shellソート³は1959年にD.L.Shellが考案した方法で、単純挿入法を改良したものとなっている。単純挿入法は、隣同士を比較しましたが、Shellソートでは、大きな

飛ばしで比較する。ソートに時間のかかる大ききな数や小さな数は、一気に右や左に移動する。

飛ばしで比較すると、

$\begin{equation*}\begin{aligned}&a[1] \leqq a[h+1] \leqq a[2*h+1] \leqq a[3*h+1]... ... a[3*h+h] \leqq a[4*h+h] \leqq a[5*h+h]\cdots \\ % \end{aligned}\end{equation*}$