2 C言語の練習

2.1 ソーティングとは

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

2.2 単純挿入法

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

2.3 shellソート

Shellソート3は1959年にD.L.Shellが考案した方法で,単純挿入法を改良したもの となっている.バブルソート法は,隣同士を比較するが,Shellソートでは,大きな$ h$ 飛ばしで比較する.ソートに時間のかかる大ききな数や小さな数は,一気に右や左に移動 する.$ h$飛ばしで比較すると,

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

と並び替える.この並び替えには単純挿入法をつかう.

そうして,とび幅$ h$をどんどん小さくし,最後は$ h=1$にすると並び替えが完了となる.この $ h$の選び方にこつがあって,小さいほうから $ 1,4,13,40,121,\cdots$

  $\displaystyle h_{i+1}=3h_i+1$   $\displaystyle h_1=1$      

とするのが良いらしい.良いというのは早いと言うことである.最初に実行する一番大きな$ h$ は,データの個数の半分以下にする.

Shellソートの手順は,次の通りである.

  1. 最初の飛び幅$ h$を決める.データの個数の半分以下で最大の$ h_i$を最初の飛び幅と する.
  2. $ i=1,2,3,\cdots,h$に対して, a[i],a[h+i],a[2*h+i],a[3*h+i],$ \cdots$を並び替える.
  3. 次のi++して,並び替える.
  4. 次のh=(h-1)/3にして,再度,並び替えを実行する.

リスト1の19行目以降にshellソートのプログラムを書き,配列を 小さい順(昇順)に並び替えよ.



ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
平成19年8月8日


no counter