【C算法】第6章 ソート (その3)

いまのやり方だと仕事との両立が早晩きつくなるような。昨日も朝までやってたし。。。

• 今日は「6-5 シェルソート」。
  
• だめだ。シェルソートのアルゴリズムがどういものだかはすぐわかるのだが、それのCによる実装が例示されているソースでよいことがわからない。
  
• 変数の動きを追ってみる。
  

  
  --------------------------------------------------------
  n:                2
        0     1
  h:          n/2
  i:          h
  j:    i-h 
  
  --------------------------------------------------------
  n:                      3
        0     1     2
  h:          n/2
  i:          h
  j:    i-h
  i:                i++
  j:          i-h
  
  --------------------------------------------------------
  n:                            4
        0     1     2     3
  h:                n/2
  i:                h
  j:    i-h
  i:                      i++
  j:          i-h
  
  h:          n/2/2
  i:          h
  j:    i-h
  i:                i++
  j:          i-h
  j:    i-2h
  i:                      i++                                                                                                                                                
  j:                i-h
  j:          i-2h
  j:    i-3h
  
  --------------------------------------------------------
  n:                                  5
        0     1     2     3     4
  h:                n/2
  i:                h
  j:    i-h
  i:                      i++
  j:          i-h
  i:                            i++
  j:                i-h
  j:    i-2h
  
  h:          n/2/2
  i:          h
  j:    i-h
  i:                i++
  j:          i-h
  j:    i-2h
  i:                      i++
  j:                i-h
  j:          i-2h
  j:    i-3h
  i:                            i++
  j:                      i-h
  j:                i-2h
  j:          i-3h
  j:    i-4h
  --------------------------------------------------------
  n:                                                    8
        0     1     2     3     4     5     6     7
  h:                            n/2
  i:                            h
  j:    i-h
  i:                                  i++
  j:           i-h
  i:                                        i++
  j:                i-h
  i:                                              i++
  j:                      i-h
  
  h:                n/2/2
  i:                h
  j:    i-h
  i:                      i++
  j:          i-h
  i:                            i++
  j:                i-h
  j:    i-2h
  i:                                  i++
  j:                      i-h
  j:          i-2h
  i:                                        i++
  j:                            i-h
  j:                i-2h
  j:    i-3h
  i:                                              i++
  j:                                  i-h
  j:                      i-2h
  j:          i-3h
  
  h:          n/2/2/2
  i:          h
  j:    i-h
  i:                i++
  j:          i-h
  j:    i-2h
  i:                      i++
  j:                i-h
  j:          i-2h
  j:    i-3h
  i:                            i++
  j:                      i-h
  j:                i-2h
  j:          i-3h
  j:    i-4h
  i:                                  i++
  j:                            i-h
  j:                      i-2h
  j:                i-3h
  j:          i-4h
  j:    i-5h
  i:                                        i++
  j:                                  i-h
  j:                            i-2h
  j:                      i-3h
  j:                i-4h
  j:          i-5h
  j:    i-6h
  i:                                              i++
  j:                                        i-h
  j:                                  i-2h
  j:                            i-3h
  j:                      i-4h
  j:                i-5h
  j:          i-6h
  j:    i-7h
  
  --------------------------------------------------------
  

  
  
• ここでhは、「h離れたものどもでソート」であり、幅のようなもの。ここでは4,2,1という数列。
  
• iは[h,n)における1刻みの数列を作る。i(q) = h + q, {q= 0, 1, ..., n - p - 1}
  これは幅hで離れたもの「ども」の尻尾にあたる要素を列挙しているのだが、それだけではない。そのモノドモごとに、単純挿入ソートをおこなうのだから、1つのモノドモをソートしきるには、そのモノドモに含まれる要素数と同じ回数だけモノドモ(の部分)をなめなければならない。iが[h,n)というように結構多いなぁという数なのはそれを尽くすためである。
  
• よって、その尽くすためのi達おのおのから幅hで減算していく数列が単純挿入ソートの対象添字セットであり、それがj。
  
• ああ、やっとわかった。
  
• わかりにくい原因は、「シェルソートのイメージはモノドモ毎にソートを完了していくというものだが、Cの実装ではソートがモノドモをまたがってインターリーブされている」というところだ。
  
• わかったこと。
  
  
  
  • このCの実装は「成すべき処理を、いかに効率よく生成するか」というものである。
    
  • なので、アルゴリズムの結果として成すべき処理が一覧されたとして、それをどう組替えるともっとも単純にそれら処理を生成できるものになるか、ということ。
    
  • そして、Cでこのように考える、ということは、おそらく「慣れ」の問題。ただし、その慣れを得るのにCでいろいろやるのがいいか、離散数学を勉強するのがいいかは要判断。
    
  • CLからプログラミングを学びはじめたので、私はこの手の思考に弱い。
    
  • ここでやった分析は手で実施したのだが、これ自体をプログラムに出力させればよい。手でやるのはアホ。
    
  
  
• 演習6-9で、(*s)++とすべきところを、*s++としてしまって、ちょっとはまった。いかんなぁ。
  
• 演習6-9。1000個の要素に0〜9999をランダムに入れてソートさせると2の倍数だと15000強の交換、3倍して1足す方だと14000強、というかんじだった。
  

こつこつ。