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

ちょっと、アルゴリズムを学ぶことが、なんだかわからなくなっている。

• クイックソートのアルゴリズムで、なぜ分割がうまくいくのか、がわからない。
  
• そういう方法で分割できる、ということは覚えれば、覚えられる。
  
• それでいいのか、どうか。
  
• それじゃ足りないとしたら、分割がわかる、というのはどういうことなのか。
  
• アルゴリズムを理解する、ということ自体がわからない。。。
  
• この方法(アルゴリズム)で、分割できることの証明を構築できればいいのかなぁ。
  
• アルゴリズムを文章で書いてみる。
  
  
  
  • 配列aがある。大きさはN。型はint。値がすべての要素に入っている。
    
  • pl=0, pr=N-1という2つのインデックスポインタをつくる。
    
  • aの中から一つ要素を選ぶ。その値をxと呼ぶ。
    
  • plはa[pl]>=xが成立する要素が見つかるまで、右側に走査する。
    
  • prはa[pr]<=xが成立する要素が見付かるまで、左側に走査する。
    
  • 走査がおわったとき、pl > prならば、処理完了。そこで、インデックスが0 〜 pl-1がx以下の要素のグループ、pr+1 〜 N-1がx以上のグループ、pl>pr+1ならばpr+1〜pl-1がxに等しいグループの3つに分割されている。
    
  • 走査がおわったとき、pl <= prならば、a[pl]とa[pr]の値を交換して再度走査を開始する。
    
  
  
• うーん。これを数学的に証明するのはちょっと面倒そうだ。場合わけが。。。
  
• そして、それはこの本の学習でやるべきことじゃなく思えてきた。それをやるなら、Knuth本とかじゃないだろうか舞台は。
  
• というわけで、クイックソートの数学的理解は、今はやめておこう。
  
• 直感的にはわかるんだけどねぇ。
  
  
• 演習6-14でひっかかる。ポインタがからむとやっぱりひっかかる。前より楽になったけど。
  
• GDBをもうちょっと便利につかいたい。UNIXプログラミングの道具箱をみる。
  
  
  
  • breakpointは関数名引数で設定すべし。
    
  • 停止毎に表示確認する式はdisplayで登録すべし。
    
  • 中身をよくみる構造体はdefineで手続化すべし。
    
  • 繰返しGDBを起動するような状況なら、作業ディレクトリに.gdbinitをおいて、必要なものはそこに書くべし。
    
  • または、-x fileをgdbにわたして、起動時に実行させるべし。
    
  • または、source fileでプロンプトから読み込むべし。
    
  
  
• てな感じ。演習6-14では、こんなんにして、sourceで読み込むことにした。
  

  
  # gdbinit file for prac0614.c
  
  display left
  display right
  display pivot
  display pl
  display pr
  
  define hookpost-next
         set $n = 0
         while $n < nmemb
               print *((int *)base + $n)
               set $n = $n + 1
         end
  end
  
  #break quick 
  #displayの設定は、そのシンボルが存在するcontextに入らないとできない。
  #なので、displayを読ませるには、先にrunする必要あり。
  # runする前にbreak quickする必要あり。
  #よってbreak quickはプロンプトでやることにする。
  

  
  
• バグバグな状態をGDBで調べてみる。
  
• 判明、あんまりよく考えないで書いていたからだけだった。。。うむー。
  
• 演習6-15。う、関数ポインタやNULLポインタをつかって、高階関数を作るときは、その関数の中身が再帰でかかれているよりも非再帰でかかれていたほうががかなり楽。
  
• 演習6-16。また間違えた。変数の値をswapしたいときにポインタをつかっていて、アドレスをコピーしちゃってて値をコピーしていない。
  

うーん。やっとクイックソートがおわった。クイックソートじゃなくて、ポインタに慣れてきた。それはそれでよし。