前回の授業では、再帰処理やソートアルゴリズムの処理時間の見積もりについて説明を行った。

ソート処理の見積もり

この際の練習問題の1つめは、「再帰方程式の理解度確認の回答」にて解説を示す。

最後の練習問題はここで説明を行う。

選択法とクイックソートの処理時間の比較

例として、データ数N=20件で、選択法なら10msec、クイックソートで20msecかかったとする。

これより、選択法の処理時間を、クイックソートの処理時間を、とすると、

よって、

処理時間が逆転するときのデータ件数は、2つのグラフの交点を求めることになるので、

より、以下の式を解いた答えとなる。これは通常の方程式では解けないが電卓で求めると、N=53.1 ほどかな。(2020/05/26) 真面目に解いたら N=53.017 だった。

実際にも、クイックソートを再帰呼び出しだけでプログラムを書くと、データ件数が少ない場合は選択法などのアルゴリズムの方が処理時間が早い。このため、C言語などの組み込み関数の qsort() などは、データ件数が20とか30とか一定数を下回ったら、再帰を行わずに選択法でソートを行うのが一般的である。

ポインタ処理

ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。

値渡し(call by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。

言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。

でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか？

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
}

ポインタ渡し(call by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
void main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
}               // さらに125と増える。

C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は：結果を入れてもらう場所を伝え、関数側は：指定されたアドレスに結果を書む。

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式) と p[ 整数式 ] は同じ意味

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

構造体とポインタ

構造体を関数に渡して処理を行う例を示す。

struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person table[3] = {
   { "t-saitoh" , 55 } ,
   { "tomoko" ,   44 } ,
   { "mitsuki" ,  19 } ,
} ;

void print_Person( struct Person* p ) {
   printf( "%s %d\n" ,
           (*p).name , // * と . では . の方が優先順位が高い
                       // p->name と簡単に書ける。
           p->age ) ;  // (*p).age の簡単な書き方
}

void main() {
   for( int i = 0 ; i < 3 ; i++ ) {
      print_Person( &(table[i]) ) ;
   // print_Person( table + i ) ; でも良い
   }
}

構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。

練習問題(2018年度中間試験問題より)