%=====================================================================
% 秋田高専 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{ソート(その3)}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2005年10月25日}
\maketitle
%
%
%=====================================================================
\section{本日の学習内容}
%=====================================================================
本日は，以下の学習を行う．
\begin{itemize}
 \item クイックソート(Quick Sort)
 \item マージソート(Merge Sort)
 \item コームソート(Comb Sort)
\end{itemize}
%
%=====================================================================
\section{クイックソート}
%=====================================================================
原理やプログラムのテクニックについては前回のプリントで示しているので，ここには記
述しない．ただし，前回のプリントで分かりにくかったクイックソートの様子を示すこと
にする．
%
%---------------------------------------------------------------------
\subsection{クイックソートの様子}
%---------------------------------------------------------------------
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.65]
  {figure/Quick_sort.eps}
  \caption{クイックソートの様子．}
  \label{fig:Quick_sort}
 \end{center}
\end{figure}
%
%=====================================================================
\section{C言語の\tw{qsort()}関数}
%=====================================================================
C言語には\tw{qsoort()}が実装されており，それはクイックソートが使われていることが
多い．そのため，実際のプログラムでは，プログラマーがソートのルーチンを記述するこ
とは希で，この\tw{qsort()}関数をつかう．お手軽なので，諸君はこれを使うのが良いだ
ろう．

この関数は，標準ライブラリー関数で，\tw{stdlib.h}をインクルードすることにより使
うことができる．プログラムの先頭付近に
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	#include <stdlib.h>
 \end{verbatim}
\end{quote}
%
と書けば，インクルードできる．

この\tw{qsort()}関数を使う場合の引数の渡し方であるが，それは教科書(Table 1-1)に
書いてあるとおりである．正確な記述は教科書の通りであるが，もう少し分かりやすく書
くと
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	void qsort(配列名, 配列の数, 配列一つのバイト数, 比較関数)
 \end{verbatim}
\end{quote}
%
となる．返値はなく，配列そのものがソートされる．引数はデータを入れてある配列に関
するものと比較関数である．

ここで，ちょっと難しいのは，比較関数の作り方である．それを，教科書の例(List 1-4)
で示すことにする．教科書の比較関数は，
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	int compare(const void *arg1,const void *arg2)
	{
	    return(*((int *)arg1)-*((int *)arg2));
	}
 \end{verbatim}
\end{quote}
%
となっている．返値は整数型と宣言されている．\tw{qsort()}関数の引数で渡す比較関数
の返値は整数と決められているので，それに従っている．問題は引数で，\tw{const}は引
数が変化しないことを明示的に示している．\tw{arg2}を左辺値として，代入文を使うと
エラーが発生する．つぎの\tw{void}は，\tw{arg1}や\tw{arg2}はポインターであるが，
その型は後で決めると言うことである．実際このプログラムでは，強制型変換(キャスト)
を使って決めている．

つぎにこの関数の計算であるが，次の文が難しい．
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
	*((int *)arg1
 \end{verbatim}
\end{quote}
%
まずこれは，\tw{(int *)arg1}で\tw{arg1}を整数型のポインターに強制的に型変換して
いる．そして，もっとも左にあるアスタリスク\tw{*}で，そのポインターが示す値を取り
出している．

ちょっと難しいが，C言語では，引数として変数のみならず関数も引数で送ることができ
るのである．
%=====================================================================
\section{マージソート}
%=====================================================================
原理やプログラムのテクニックについては前回のプリントで示しているので，ここには記
述しない．ただし，前回のプリントで分かりにくかったマージソートの様子を示すこと
にする．
%
%---------------------------------------------------------------------
\subsection{マージソートの様子}
%---------------------------------------------------------------------
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.65]
  {figure/merge_sort.eps}
  \caption{マージソートの様子．}
  \label{fig:merge_sort}
 \end{center}
\end{figure}
%=====================================================================
\section{コームソート}
%=====================================================================
%---------------------------------------------------------------------
\subsection{方法}
%---------------------------------------------------------------------
バブルソートに似た方法であるが，比較する対象が異なる．
\begin{itemize}
 \item バブルソートは，いつでもとなり同士と比較し，大小関係が異なれば交換する．
 \item コームソートは，はじめは遠くのものと比較し，だんだん比較の間隔を狭くする．
       最後には，バブルソートと同じようにとなり同士と比較をする．
\end{itemize}
バブルソートの最大の欠点は，ソートが遅いことである．小さな値は左に一つずつしか，
移動できないためである．なぜならば，いつもとなり同士を比較するため，交換はとなりとし
かできないからである．

この問題の解決を図るために，最初大きな間隔(ギャップ)で比較して，大きなステップで
移動させるのがコームソートである．そして，だんだん間隔を狭くして，ソートを完了さ
せるのである．
%---------------------------------------------------------------------
\subsection{プログラムテクニック}
%---------------------------------------------------------------------
\paragraph{グローバル関数}
教科書のList 1-6では，ソートする配列はグローバル変数となっており，どの関数からで
もアクセスできるようになっている．ここで使われている\tw{CombSort()}関数と
\tw{main()}関数の外側で，配列\tw{sort[N]}は宣言されている．このように，関数の外
側で宣言された変数はグローバル変数と呼ばれ，どの関数からでもアクセスできる．

\paragraph{返値無しの関数}
\tw{CombSort()}は，値を返さない関数である．この場合，返値の型として，
\tw{void}と宣言をする．voidとは，"空の"という意味である．

\paragraph{引数無しの関数}
\tw{CombSort()}は，引数のない関数である．この場合は，引数の型として，\tw{void}と
宣言する．
%---------------------------------------------------------------------
\subsection{コームソートの様子}
%---------------------------------------------------------------------
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.65]
  {figure/comb_sort.eps}
  \caption{コームソートソートの様子．}
  \label{fig:comb_sort}
 \end{center}
\end{figure}
%=====================================================================
\section{単純挿入ソート}
%=====================================================================
これは，夏休みの課題のプログラムである．
%=====================================================================
\section{2分挿入ソート}
%=====================================================================
教科書に沿って説明する．
%=====================================================================
\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}
%

ただし，ソートする数列は出席番号により異なる．
%
\begin{itemize}
 \item 学籍番号の下1桁が1〜9の場合，その数から10個の数列をソートする．たとえば，
       下一桁が3の場合は，
%
       \begin{quote}
	\begin{small}
	 \begin{verbatim}
	608 239 956 244 535 840 629 353 784 199
	 \end{verbatim}
	\end{small}
       \end{quote}
である．
\item 学籍番号の下1桁が0の場合，その10番目から10個の以下の数列をソートする．
%
       \begin{quote}
	\begin{small}
	 \begin{verbatim}
	353 784 199 945 847 637 413 686 172 462
	 \end{verbatim}
	\end{small}
       \end{quote}
%
\end{itemize}

\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi]マージソートで昇順の場合
  \item[\toi]コームソートで昇順の場合
 \end{itemize}
\end{quote}
%-----------------------------
\subsubsection{プログラムの変更}
%-----------------------------
教科書のマージソートのプログラム(List 1-5)，コームソートのプログラム(List 1-6)は，
いずれの場合も昇順に並び替えるようになっている．降順(大きい順)に並び替えするよう
なプログラムに変更したい．以下の問いに答えよ．
\begin{quote}
 \begin{itemize}
  \item[\toi]マージソートのプログラム(List 1-5)のどこをどのように変更するか?
  \item[\toi]コームソートのプログラム(List 1-6)のどこをどのように変更するか?
 \end{itemize}
\end{quote}
%
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は、次の通りとする。
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 11月7日(月) AM 8:50 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\
       & \qquad 授業科目名「情報工学」\\
       & \qquad 課題名「課題　ソート(その3)」\\
       & \qquad 2E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%
%
\newpage
%=====================================================================
%  参考文献
%=====================================================================
%\bibliographystyle{jplain}
%\bibliography{reference}
%=====================================================================
\end{document}