2 クイックソート

2.2 プログラムテクニック

教科書に書かれているプログラムのテクニックを説明する．main関数から見ていって，諸君にわかりにくいものを説明する．

2.2.1 乱数

乱数とは、バラバラな数列のことを言う。とくに、自然数がめちゃくちゃに現れるようなものを自然乱数という。0以上無限大までの全ての自然数を用いた自然乱数が考えられるが、実際上は最大の自然数を決め、その範囲で考えることが多い。0～RAND_MAXの範囲で乱数を発生させることができる．RAND_MAXはstdlib.hに書かれており，私が使用しているシステムのC言語の場合、

/* The largest number rand will return (same as INT_MAX).  */
#define	RAND_MAX	2147483647

となっている．したがって，0～2147483647の範囲²の乱数を発生させることができるのである。

C言語のプログラムでは、rand()関数を使って、乱数を発生させる。教科書のプログラムでは、rand()関数が呼び出される度に、それが乱数を返し、配列sort[i]に格納される。

コンピューターは正確に言われたとおり(プログラムのとおり)に計算を行うことは、諸君もよく知っているはずである。そのため、コンピューターはめちゃくちゃな順序で数が並んでいる乱数を発生させることは苦手である。先ほどのrand()関数は、ある初期値 ³を使って、計算により乱数を決めている。同じ初期値を使って、rand()関数を呼び出すと、同じ数列が発生するこのになる。これでは、乱数とは言い難いので、初期値を毎回変更するのがよい。

初期値も値が毎回異なる整数を決める必要があるが、現在の暦時刻を返すtime()関数を用いるのが一般的である。初期値の設定は、srand()関数に引数(符号無し整数) を渡すことにより可能である。次のようにすれば、毎回異なる初期値を決めることができる。

ただし、1秒以内であれば、timeは同じ値となり、同じ初期値となり、同じ乱数となることに注意が必要である。(unsigned int)は、キャストと呼ばれる強制型変換で、引き続く値の型を変換している。time()関数の引数は暦時刻で、暦時刻がポインターで格納される。暦時刻を格納する必要がないときには、NULLと空ポインターを指定する。

以上から、乱数を発生させるためには、rand()とsrand()、time()関数が必要であることが分かった。これらの関数を使うためには、関数の宣言が書かれているヘッダーファイルが必要である。rand()とsrand()にはstdlib.hが、 time()にはtime.hが必要となる。

2.2.2 その他

関数QuickSortのプロトタイプ宣言が書かれていない．
関数が使われる前に，関数の定義を書くとプロトタイプ宣言を書かなくても良い．コンパイラーはソースコードのはじめから，機械語に変換するので，最初に関数の内容が分かれば，関数の使われ方があらかじめ分かる．関数を使うときに，引数のチェックが可能である．一方，関数の定義よりも前に，関数が使われると，プロトタイプ宣言がないと引数のチェックができない．
return EXIT_SUCCESS;
このEXIT_SUCCESSはstdlib.hに定義されているマクロで，私のパソコンでは
```
	#define	EXIT_SUCCESS	0	/* Successful exit status.  */
```
となっている．したがって，これは，
```
	return 0;
```
と書くのと同じである．
while文に括弧{}がない．
プログラム中に，
```
	while(lower<=upper&&data[lower]<=div)
	    lower++;
```
と書かれている．これは，
```
	while(lower<=upper&&data[lower]<=div){
	    lower++;
	}
```
と書くのと同一である．C言語では，2つ以上の文をひとまとめにすることがでる．これは，コードブロックまたは複文と呼ばれる構造である．コードブロックを作るには，まとめたい文を{}で囲みます．{ここに複数の文}で囲んだコードブロックは，ひとつの論理的なまとまりであり，単一の文が書けるところならどこでも使うことができる．

2.3 ソートの様子

実際にソートした結果を示す．

ソート準備:
879 269 649 711 435 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531

ソート開始:
879 269 649 711 435 311 701 605 303 879 857 419 298 278 817 713 531 469 832 983
832 269 649 711 435 311 701 605 303 879 857 419 298 278 817 713 531 469 879 983

832 269 649 711 435 311 701 605 303 469 857 419 298 278 817 713 531 879 879 983
832 269 649 711 435 311 701 605 303 469 531 419 298 278 817 713 857 879 879 983
713 269 649 711 435 311 701 605 303 469 531 419 298 278 817 832 857 879 879 983

278 269 649 711 435 311 701 605 303 469 531 419 298 713 817 832 857 879 879 983

269 278 649 711 435 311 701 605 303 469 531 419 298 713 817 832 857 879 879 983

269 278 649 298 435 311 701 605 303 469 531 419 711 713 817 832 857 879 879 983
269 278 649 298 435 311 419 605 303 469 531 701 711 713 817 832 857 879 879 983
269 278 531 298 435 311 419 605 303 469 649 701 711 713 817 832 857 879 879 983

269 278 531 298 435 311 419 469 303 605 649 701 711 713 817 832 857 879 879 983
269 278 303 298 435 311 419 469 531 605 649 701 711 713 817 832 857 879 879 983

269 278 298 303 435 311 419 469 531 605 649 701 711 713 817 832 857 879 879 983

269 278 298 303 419 311 435 469 531 605 649 701 711 713 817 832 857 879 879 983

269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983

269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983

269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983


ソート終了:
269 278 298 303 311 419 435 469 531 605 649 701 711 713 817 832 857 879 879 983

ホームページ: Yamamoto's laboratory
著者: 山本昌志

Yamamoto Masashi
平成17年10月27日

2 クイックソート

2.1 手順

2.2 プログラムテクニック

2.2.1 乱数

2.2.2 その他

2.3 ソートの様子