%===================================================================== % 秋田高専 2E 情報工学概論 テキスト %　　テーマ　ソート % 本テキストの内容 % ・ % ・ % ・ % ・ %　　　 　・ % % last updated 2005.6.23 % created by Masashi Yamamoto % e-mail yamamoto@akita-nct.jp %===================================================================== \documentclass[10pt,a4paper]{jarticle} \usepackage{graphicx,amsmath,amssymb,ascmac,float} \usepackage{html, listings, jlisting} \oddsidemargin 0mm %左の余白 25.4mm-0mm　奇数ページ \evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ \textwidth 160mm \newcommand{\command}[1]{「\texttt{#1}」} \newcommand{\cl}[1]{\texttt{#1}} \newcommand{\tw}[1]{\texttt{#1}} % \newcounter{toi_num} \newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]} \addtocounter{toi_num}{1}} \newcommand{\qbox}[1]{ {\fboxsep=2pt\fboxrule=0.4pt\fbox{\hspace{3mm}{#1}\hspace{3mm}}} } % \renewcommand{\lstlistingname}{リスト} \lstset{language=C,% basicstyle=\footnotesize,% commentstyle=\textit,% classoffset=1,% keywordstyle=\bfseries,% frame=tRBl,framesep=5pt,% showstringspaces=false,% numbers=left,stepnumber=1,numberstyle=\footnotesize% }% % \begin{htmlonly} \usepackage{verbatimfiles} \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}} \end{htmlonly} % \begin{document} \title{ソート(その2)} \author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}} \date{2005年10月18日} \maketitle % % %===================================================================== \section{本日の学習内容} %===================================================================== 本日は，以下の学習を行う． \begin{itemize} \item クイックソート \item マージンソート \end{itemize} % %===================================================================== \section{クイックソート} %===================================================================== %--------------------------------------------------------------------- \subsection{手順} %--------------------------------------------------------------------- ここは教科書を使って説明する． % %--------------------------------------------------------------------- \subsection{プログラムテクニック} %--------------------------------------------------------------------- 教科書に書かれているプログラムのテクニックを説明する．\tw{main}関数から見ていっ て，諸君にわかりにくいものを説明する． %------------------- \subsubsection{乱数} %------------------- 乱数とは、バラバラな数列のことを言う。とくに、自然数がめちゃくちゃに現れるよう なものを自然乱数という。0以上無限大までの全ての自然数を用いた自然乱数が考えられ るが、実際上は最大の自然数を決め、その範囲で考えることが多い。0〜\tw{RAND\_MAX}の 範囲で乱数を発生させることができる．\tw{RAND\_MAX}は\tw{stdlib.h}に書かれており， 私が使用しているシステムのC言語の場合、 \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} /* The largest number rand will return (same as INT_MAX). */ #define RAND_MAX 2147483647 \end{verbatim} \end{quote}\vspace{-3mm} となっている．したがって，0〜2147483647の範囲\footnote{0〜2$^31$-1の範囲である。}の 乱数を発生させることができるのである。 C言語のプログラムでは、\tw{rand()}関数を使って、乱数を発生させる。教科書のプログ ラムでは、\tw{rand()}関数が呼び出される度に、それが乱数を返し、配列\tw{sort[i]}に 格納される。 コンピューターは正確に言われたとおり(プログラムのとおり)に計算を行うことは、諸君 もよく知っているはずである。そのため、コンピューターはめちゃくちゃな順序で数が並 んでいる乱数を発生させることは苦手である。先ほどの\tw{rand()}関数は、ある初期値 \footnote{正確にはseed(種)と言うらしい。}を使って、計算により乱数を決めている。 同じ初期値を使って、\tw{rand()}関数を呼び出すと、同じ数列が発生するこのになる。 これでは、乱数とは言い難いので、初期値を毎回変更するのがよい。 初期値も値が毎回異なる整数を決める必要があるが、現在の暦時刻を返す\tw{time()}関 数を用いるのが一般的である。初期値の設定は、\tw{srand()}関数に引数(符号無し整数) を渡すことにより可能である。次のようにすれば、毎回異なる初期値を決めることができる。 ただし、1秒以内であれば、\tw{time}は同じ値となり、同じ初期値となり、同じ乱数とな ることに注意が必要である。\tw{(unsigned int)}は、キャストと呼ばれる強制型変換で、 引き続く値の型を変換している。\tw{time()}関数の引数は暦時刻で、暦時刻がポインター で格納される。暦時刻を格納する必要がないときには、\tw{NULL}と空ポインターを指定 する。 以上から、乱数を発生させるためには、\tw{rand()}と\tw{srand()}、\tw{time()}関数が 必要であることが分かった。これらの関数を使うためには、関数の宣言が書かれているヘッ ダーファイルが必要である。\tw{rand()}と\tw{srand()}には\tw{stdlib.h}が、 \tw{time()}には\tw{time.h}が必要となる。 % %-------------------- \subsubsection{その他} %-------------------- \begin{itemize} \item 関数\tw{QuickSort}のプロトタイプ宣言が書かれていない． \begin{quote} 関数が使われる前に，関数の定義を書くとプロトタイプ宣言を書かなくても良 い．コンパイラーはソースコードのはじめから，機械語に変換するので，最初に 関数の内容が分かれば，関数の使われ方があらかじめ分かる．関数を使うときに， 引数のチェックが可能である．一方，関数の定義よりも前に，関数が使われると， プロトタイプ宣言がないと引数のチェックができない． \end{quote} \item \tw{return EXIT\_SUCCESS;} \begin{quote} この\tw{EXIT\_SUCCESS}は\tw{stdlib.h}に定義されているマクロで，私のパソ コンでは \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} #define EXIT_SUCCESS 0 /* Successful exit status. */ \end{verbatim} \end{quote}\vspace{-3mm} となっている．したがって，これは， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} return 0; \end{verbatim} \end{quote}\vspace{-3mm} と書くのと同じである． \end{quote} \item \tw{while}文に括弧\tw{\{\}}がない． \begin{quote} プログラム中に， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} while(lower<=upper&&data[lower]<=div) lower++; \end{verbatim} \end{quote}\vspace{-3mm} と書かれている．これは， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} while(lower<=upper&&data[lower]<=div){ lower++; } \end{verbatim} \end{quote}\vspace{-3mm} と書くのと同一である．C言語では，2つ以上の文をひとまとめにすることがでる． これは，コードブロックまたは複文と呼ばれる構造である．コードブロックを作るには， まとめたい文を\tw{\{\}}で囲みます．\tw{\{ここに複数の文\}}で囲んだコード ブロックは，ひとつの論理的なまとまりであり，単一の文が書けるところならど こでも使うことができる． \end{quote} \end{itemize} %--------------------------------------------------------------------- \subsection{ソートの様子} %--------------------------------------------------------------------- % 実際にソートした結果を示す． \begin{quote} \begin{small} \begin{verbatim} ソート準備: 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 \end{verbatim} \end{small} \end{quote} % %===================================================================== \section{マージソート} %===================================================================== %--------------------------------------------------------------------- \subsection{手順} %--------------------------------------------------------------------- ここは教科書を使って説明する． % %--------------------------------------------------------------------- \subsection{プログラムテクニック} %--------------------------------------------------------------------- \begin{itemize} \item \tw{x[k++]=buffer[i++];} \begin{quote} これは，後値型のインクリメント演算子を用いており， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} x[k]=buffer[i]; i++; k++; \end{verbatim} \end{quote}\vspace{-3mm} とおなじである．反対に，前値型のインクリメント演算子を用いると， \tw{x[++k]=buffer[++i];}は， \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} i++; k++; x[k]=buffer[i]; \end{verbatim} \end{quote}\vspace{-3mm} と同一の働きとなる． \end{quote} \item 引数で配列名を渡すところに，\tw{x+m}となっている \begin{quote} 配列名は，配列の先頭を示すポインターである．したがって，配列名\tw{x}に整 数\tw{m}を加算するということは，ポインターを\tw{m}だけ移動させたことにな る．したがって，\tw{x+m}は\tw{x[m]}を表すポインターとなっている． \end{quote} \end{itemize} % %--------------------------------------------------------------------- \subsection{ソートの様子} %--------------------------------------------------------------------- 実際にソートした結果を示す． \begin{quote} \begin{small} \begin{verbatim} ソート準備: 879 269 649 711 435 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 ソート開始: 269 879 649 711 435 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 879 649 435 711 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 879 435 649 711 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 435 649 711 879 311 701 605 303 879 857 419 298 278 817 713 983 469 832 531 269 435 649 711 879 311 701 303 605 879 857 419 298 278 817 713 983 469 832 531 269 435 649 711 879 303 311 605 701 879 857 419 298 278 817 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 857 419 298 278 817 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 419 857 298 278 817 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 419 857 298 278 817 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 419 857 278 298 817 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 832 531 269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 531 832 269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 713 983 469 531 832 269 303 311 435 605 649 701 711 879 879 278 298 419 817 857 469 531 713 832 983 269 303 311 435 605 649 701 711 879 879 278 298 419 469 531 713 817 832 857 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 \end{verbatim} \end{small} \end{quote} % %===================================================================== \section{課題} %===================================================================== %--------------------------------------------------------------------- \subsection{課題内容} %--------------------------------------------------------------------- %--------------------- \subsubsection{ソート} %--------------------- 以下の数列のソートに関する問題である．これをそれぞれにソートで並び替えを行った場 合，その様子を示せ．この講義ノートの「ソートの様子」で示したように記述すれば良い． ただし，様子は手書きで書くこと． \begin{quote} \begin{small} \begin{verbatim} 752 778 608 239 956 244 535 840 629 353 784 199 945 847 637 413 686 172 462 223 \end{verbatim} \end{small} \end{quote} \setcounter{toi_num}{1} \begin{quote} \begin{itemize} \item[\toi]バブルソートで昇順(小さい順)の場合．この場合は，先頭から端まで1回の ソート毎の数列の並びを書くだけでよい． \item[\toi]クイックソートで昇順の場合 \item[\toi]マージソートで昇順の場合 \end{itemize} \end{quote} %----------------------------- \subsubsection{プログラムの変更} %----------------------------- 教科書のバブルソートのプログラム(List 1-1)，クイックソートのプログラム(List 1-3)， マージソートのプログラム(List 1-5)は，いずれの場合も昇順に並び替えるようになって いる．降順(大きい順)に並び替えするようなプログラムに変更したい．以下の問いに答え よ． \begin{quote} \begin{itemize} \item[\toi]バブルソートのプログラム(List 1-1)のどこをどのように変更するか? \item[\toi]クイックソートのプログラム(List 1-3)のどこをどのように変更するか? \item[\toi]マージソートのプログラム(List 1-5)のどこをどのように変更するか? \end{itemize} \end{quote} % %--------------------------------------------------------------------- \subsection{レポート提出要領} %--------------------------------------------------------------------- 提出方法は、次の通りとする。 % \begin{quote} \begin{tabular}{ll} 期限 & 10月24日(月) AM 8:50 \\ 用紙 & A4 \\ 提出場所 & 山本研究室の入口のポスト \\ 表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\ & \qquad 授業科目名「情報工学」\\ & \qquad 課題名「課題　ソート(その2)」\\ & \qquad 2E\quad 学籍番号\quad 氏名\\ & \qquad 提出日\\ 内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること． \end{tabular} \end{quote} % % \newpage %===================================================================== \section{付録} %===================================================================== %--------------------------------------------------------------------- \subsection{クイックソートの計算量} %--------------------------------------------------------------------- \tw{QuickSort()}関数が最初に呼び出されたときの比較 % \begin{quote} \setlength{\baselineskip}{12pt} \begin{verbatim} lower<=upper&&data[lower]<=div lower<=upper&&data[upper]>div \end{verbatim} \end{quote} % の実行回数 は、$N+1$回である。そして、再帰 呼び出しにより、$\alpha$ 個と$\beta$個の場合の\tw{QuickSort()}が呼び出されることにな る。$N$個の時のトータルの比較回数を$a_N$として、これらの関係は、 \begin{align} a_N=N+1+a_\alpha+a_\beta \end{align} となる。もちろん、$\alpha$と$\beta$は、$1$〜$N-1$の値を取りうる。そして、 \tw{sort[]}に格納されている値がランダムであれば、同じ確率で$1$〜$N-1$の値をとる。さ らに、$\alpha$と$\beta$の和は$N$になることはクイックソートのアルゴリズムから自明 である。したがって、$a_N$の期待値は、 \begin{align} a_N&=N+1+\frac{1}{N-1}\left(a_1+a_2+a_3+\cdots+a_{N-1} +a_{N-1}+a_{N-2}+a_{N-3}+\cdots+a_1\right)\nonumber \\ &=N+1+\frac{2}{N-1}\sum_{k=1}^{N-1}a_k \label{eq:qsort_1} \end{align} となる。この漸化式から、$a_N$を求めることになるが、計算は結構大変である。まず、 式(\ref{eq:qsort_1})を \begin{align} (N-1)a_N=(N+1)(N-1)+2\sum_{k=1}^{N-1}a_k \label{eq:qsort_2} \end{align} と変形しておく。つぎに、この式の$N$を$N-1$にした場合の式 \begin{align} (N-2)a_{N-1}=N(N-2)+2\sum_{k=1}^{N-2}a_k \label{eq:qsort_3} \end{align} を利用する。式(\ref{eq:qsort_2})から式(\ref{eq:qsort_3})の辺々を差し引いて整理す ると、 \begin{align} (N-1)a_N-(N-2)a_{N-1}&=(N+1)(N-1)-N(N-2)+2a_{N-1} \end{align} となる。さらに、整理を進めると \begin{align} (N-1)a_N-Na_{N-1}&=2N-1 \end{align} となる。両辺を、$(N-1)N$で割ると、 \begin{align} \frac{a_N}{N}-\frac{a_{N-1}}{N-1} &=\frac{2N-1}{(N-1)N}\nonumber \\ &=\frac{1}{N}+\frac{1}{N-1} \end{align} となる。ここで、$a_N/N$を$b_N$と置くと、 \begin{align} b_N-b_{N-1}=\frac{1}{N}+\frac{1}{N-1} \end{align} となり、階差数列を用いて容易に計算できる。すなわち、 \begin{align} b_N=b_2+\sum_{k=3}^N\left(\frac{1}{k}+\frac{1}{k-1}\right) \end{align} である。$a_2=3$より、$b_2=3/2$となるので、 \begin{align} b_N&=\frac{3}{2}+\sum_{k=3}^N\frac{1}{k}+\sum_{k=3}^N\frac{1}{k-1} \nonumber \\ &=\frac{3}{2}+\left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{2}\right)+ \left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{N}\right) \nonumber \\ &=-\frac{3}{2}-\frac{1}{N}+2\sum_{k=1}^N\frac{1}{k} \end{align} となる。ここで、$N$が大きい場合、$\sum_{k=1}^N\frac{1}{k}$は$\log_eN+\gamma$に近 づくことが知られている\footnote{通常は、 $1+\frac{1}{2}+\frac{1}{3}+\cdots-\log_eN=\gamma$という関係式を憶えている}。 $\gamma$はオイラー数と言われる定数で、その値は0.577$\cdots$である。したがって、 $N$が大きい場合、 \begin{align} b_N\simeq-\frac{3}{2}-\frac{1}{N}+2(\log_eN+\gamma) \end{align} となる。右辺の$\log_eN$は他の項に比べて大きな値を取る\footnote{通常ソートが使わ れるのは大きなサンプルがあるときである。$N=10000$を考えれば、$\log_2N$の項が支配 的であることはすぐに分かる}。したがって、 \begin{align} b_N\simeq 2\log_eN \end{align} となる。$b_N$の定義から、 \begin{align} a_N \simeq 2N\log_eN \end{align} となる。 $a_N$は\tw{sort[]}の要素の比較回数を表す。したがって、$N$が大きい場合の比較回数は、 $2N\log_eN$となる。 %===================================================================== % 参考文献 %===================================================================== \bibliographystyle{jplain} \bibliography{reference} %===================================================================== \end{document}