%===================================================================== % 秋田高専 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}} % % \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{バブルソート(その1)} \author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}} \date{2005年10月4日} \maketitle % % %===================================================================== \section{本日の学習内容} %===================================================================== 本日は，以下の学習を行う． \begin{itemize} \item アルゴリズムとデータ構造とは何か \item バブルソート \end{itemize} % %===================================================================== \section{アルゴリズムとデータ構造} %===================================================================== これからの授業では，アルゴリズムとデータ構造について学ぶ．アルゴリズムやデータ構 造の実際を学ぶ前に，これらの言葉について簡単に説明しておく． %--------------------------------------------------------------------- \subsection{アルゴリズムとはなにか} %--------------------------------------------------------------------- 1年生の時に，「アルゴリズムとは、問題を解く手順である」と学習したはずである．参 考文献\cite{algorithm_data_ishihata}には以下のように書かれており，より正確であろう． % \begin{quote} アルゴリズム(algorithm， \textbf{算法}ということもある)は， 問題を解くための手順 を定めたものである．この手順は，どのような操作をどのような順序で行うかを，曖昧な 点の残らないようにきちんと定めたものでなければならない． 手順を明確に定めてあれば，計算機をその手順通り動かして問題を解かせることができ る．アルゴリズムという概念自身は計算機と無関係に成立するが，ふつうは計算機に問 題を解かせるための手順を示す． \end{quote} % これから，諸君は計算機で問題を解く手順を学習するのである．問題の解き方はいろいろ あるけれども，効率の良いアルゴリズムを学習することになる．そして，初めてプログラ ムを作成する基礎が出来上がる． 効率とは何かという問題が生じるが，それは大体 \begin{itemize} \item 計算の早い方が良いアルゴリズムである． \item 使用するメモリーがすくない方が良いアルゴリズムである． \end{itemize} と思えばよい．諸君は，計算速度を上げるためには，クロックスピードの高いコンピュー ターを使うことを思い浮かべるかもしれないが，それによるアップは大したことはない． クロックスピードを倍にしても，2倍程度の処理の向上しか見込めない．アルゴリズムの 良し悪しにより，10倍や100倍の処理速度差が瞬く間に生じることがある．処理のスピー ドアップには，アルゴリズムが最も重要である． 良いアルゴリズムは，経験を通して身につけるものであるが，基本的なものによく研究さ れている．そこで，本講義では非常に基本的なアルゴリズムを学習して，将来の応用力を身 につけてもらいたい．基礎がわかっていないと，応用は絶対に不可能である． % %--------------------------------------------------------------------- \subsection{データ構造とはなにか} %--------------------------------------------------------------------- データ構造(data structure)とは，データのメモリー上の表現方法のことを言う．ただ， アセンブラ言語を除いて，直接メモリーのアドレスを指定して，データを操作するような ことはない．変数や配列，あるいは構造体というものを通して，データを操作することに なる． 早いアルゴリズムを実現しようとすると，データの表現方法が重要になる．たとえば， 100個の相異なる整数があって，ある値と一致するものを探すとする．このデータをふつ うの変数に入れたならば，プログラムは大変だし，それの探索(サーチ)の方法も難しいだろう． 配列に入れたならば，ある程度サーチは簡単になる．しかし，データを小さい順に整頓す ればサーチはより簡単になるだろう．データが100個程度ならば，整列の御利益はそんな に大きくないが，100万個くらいになると，かなりのスピードの差が生じる．値を小さい 順に並べるというデータ構造にすると，格段にサーチのスピードアップが図れるのである． このように，データを並び替えるだけで，サーチのスピードアップが図れるのであるが， 並び替えの時間がかかることを忘れてはならない．ただの1回しか，サーチを行わないの であれば，並び替えの時間だけ無駄に終わることになる．その場合は，並び替えを行わな いで，配列の端から探索する方が良いだろう．このように問題に応じて，なにが良いか を考えなくてはならない． 探索の回数が多くなると，並び替えを行ったデータ構造の方が有利であることは，明らか であろう．アルファベット順に並んでいない辞書は，使えないであろう．ただし，1回し か単語を探さないのであれば，単語をアルファベット順に並べる方が大変である． データの並び替えにも手間がかかるのは言うまでもない．これよりも，さらに重要なこと は，整列されたデータ構造の場合，データの追加にも手間がかかるのである．これらのバ ランスを考えて，データ構造を構築しなくてはならない．この手間のことをコスト(cost: 費用)と表現することもある．データがバラバラに並んだ配列と，小さい順(昇順)に並ん だデータ構造を比較すると，それぞれのコストは，表\ref{table:cost_data}のようにな る． \begin{table}[H] \begin{center} \caption{バラバラのデータと昇順に並んだデータのコストの比較} \label{table:cost_data} \begin{tabular}{|l|lll|} \hline & \multicolumn{3}{|c|}{コスト}\\ \cline{2-4} \multicolumn{1}{|c}{データ構造} & \multicolumn{1}{|c}{並び替え} & \multicolumn{1}{c}{データの追加}& \multicolumn{1}{c|}{探索}\\ \hline\hline バラバラのデータ & ゼロ & きわめて低い & 大 \\ 昇順のデータ & 大 & 大 & 小 \\ \hline \end{tabular} \end{center} \end{table} 問題解決のためのトータルのコストが最小の場合，もっとも良いのアルゴリズムであるし データ構造でもある．そして，最後にはコストの評価が問題となる．これは，大体計算回 数と同じようなものと考えて良い．ただ，正確にこれを評価するには非常に難しい．実際 には，いろいろなデータでプログラムをテストして，その実行時間を計るのがもっとも正 確な方法と思われる．いつも，プログラムを作ってテストするわけにはいかないので，大 体のコストの計算方法も，ここでは学習の範囲である．ただ，これについては，諸君の数 学の知識では，まだ理解できないことも多いので，あまり難しいことは言わないように心 がける． % %===================================================================== \section{バブルソート} %===================================================================== %--------------------------------------------------------------------- \subsection{手順とプログラム} %--------------------------------------------------------------------- ここは教科書を使って説明する． このアルゴリズムの特徴は， \begin{itemize} \item もっとも値の大きいデータは，外側の1回のループで右端に移動する． \item 小さい値で，左に移動すべきデータは，一つずつしか移動できない．この一つず つしか移動できないので，整列に多くの計算回数が必要となる． \item 左に移動するデータのうち，初期位置と整列終了位置との差の最大なものにより， 計算回数は決まる． \end{itemize} %--------------------------------------------------------------------- \subsection{計算量} %--------------------------------------------------------------------- 教科書のアルゴリズム(プログラム)の計算量を計算する．このプログラムの計算量は，内 側のループの回数,すなわち，大小の比較回数 \begin{align} \text{\tw{if(sort[i]>sort[i+1])}} \end{align} の実行回数で評価できるであろう．なにしろ，プログラム中もっとも実行回数の多い命令 は，この文であるからである． この文の最小実行回数は，最初から整列できている場合である．このときの，実行回数は， $N-1$回であるのは明らかである．最悪の場合は，最小の値が右端にある場合である．こ の場合の実行回数は，$(N-1)^2$となる．なぜならば， \begin{itemize} \item この最小の値は，1回外側のループ(\tw{do}文のところ)を実行する毎に，一つ左に移動する． \item 所定の位置に移動するために，$N-1$回，外側のループを実行する必要がある． \item 外側のループを1回実行する毎に，内側のループは$N-1$回，実行される． \end{itemize} となるからである． 最初のデータの並び方により，$N-1$回から$(N-1)^2$まで開きがある．初期位置と整列終 了位置との差の最大の期待値を計算することになるが，これが難しい．まだ，ちゃんとし た計算が出来ていないので，正確なことは言えないが，大体，それは$(N-2)/2$程度であ ることは分かるだろう．最小な値の初期位置と整列終了位置との差の期待値である．この 程度とすると，先の比較の実行回数は， \begin{align} \frac{(N-1)(N-2)}{2}=\frac{N^2}{2}-\frac{3}{2}N+1 \end{align} となる．データ数$N$が大きい場合，$N^2$に比例して計算量が増加する． この$N^2$に比例して計算量が必要なばあい，$O(N^2)$と書く．この表記法を \textbf{$O$記法}($O$-notation)といい，計算オーダーを示す．数学で使うランダウの記 号に似ている． かなりいい加減な説明で，バブルソートの計算回数が$O(N^2)$と示した．もっと正確に， 説明したかったが，計算方法を思いつかなかった．ネットでも正確な記述を見つけること が出来なかった．正確な計算方法が分かれば，もう一度，説明する． % %--------------------------------------------------------------------- \subsection{まとめ} %--------------------------------------------------------------------- ここで示したように，バブルソートは$O(n^2)$の計算オーダーなので，次週で述べるクイッ クソートに比べて，効率の悪いアルゴリズムである．したがって，実際問題で，このソー トは使ってはならないとされている．ただ，アルゴリズムが単純なので，最初の学習に はちょうど良いので取り上げられるが，ただ，使い道はそれだけである． % %===================================================================== \section{課題} %===================================================================== %--------------------------------------------------------------------- \subsection{課題内容} %--------------------------------------------------------------------- リスト\ref{prog:buble_sort}の続きを書いて，配列\tw{a[N]}に格納されている整数を昇 順に並び替えるプログラムを作成すること．ただし，プログラムは，以下の要領で作成す ること． \begin{itemize} \item バブルソートの部分は，独立な関数とすること． \item その関数には引数を使って，データを渡すこと．グローバル変数を使ってはなら ない．教科書ではグローバル変数を使っているので，そのまねをしないこと． \end{itemize} \lstinputlisting[caption=バブルソートのプログラム作成,label=prog:buble_sort] {program/buble_sort.c} %--------------------------------------------------------------------- \subsection{レポート提出要領} %--------------------------------------------------------------------- 提出方法は、次の通りとする。 % \begin{quote} \begin{tabular}{ll} 期限 & 10月17日(月) AM 8:50 \\ 用紙 & A4 \\ 提出場所 & 山本研究室の入口のポスト \\ 表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\ & \qquad 授業科目名「情報工学」\\ & \qquad 課題名「課題　バブルソート」\\ & \qquad 2E\quad 学籍番号\quad 氏名\\ & \qquad 提出日\\ 内容 & ソースプログラム(プリントアウトでも、手書きでもOKとする)\\ & 作成したバブルソートの関数の引数の説明 \end{tabular} \end{quote} % %===================================================================== % 参考文献 %===================================================================== \bibliographystyle{jplain} \bibliography{reference} %===================================================================== \end{document}