%=====================================================================
% 秋田高専 2E 情報工学概論 テキスト
%　　テーマ　ソート4
%    本テキストの内容
%        ・
%        ・
%        ・
%        ・
%　　　 　・
%
% last updated 2005.10.06
%    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{ソート(その4)}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2005年11月07日}
\maketitle
%
%
%=====================================================================
\section{本日の学習内容}
%=====================================================================
\begin{itemize}
\item 単純挿入ソート
\item 2分挿入ソート
\end{itemize}
%
%=====================================================================
\section{単純挿入ソート}
%=====================================================================
原理については，教科書に分かりやすくかかれているので，それを使って説明する．説明するまでもなく，教科書を一読すれば，直ちに原理は理解できるであろう．

計算量のオーダーについて，簡単に説明する．左から$i$個，整列が完了して，$i+1$個目を整列させることを考える．
\begin{itemize}
\item 数列の$i+1$番目が挿入されるべき位置を見つけるための比較の平均回数(期待値)は，$i/2$である．
\item 位置が見つかった場合，それを挿入するために，配列は平均で$i/2$の交換が必要である．
\end{itemize}
このことから，数列の$i+1$番目を正しい位置に挿入するためには，合わせて$i$回の計算\footnote{ここでは，比較と配列の交換を計算と言っている．}が必要となる．大きさが$N$の数列全体では，
%
\begin{align}
  \sum_{i=1}^{N-1}i&=\frac{(N-1)(N-2)}{2}\nonumber\\
  &=\frac{1}{2}N^2-\frac{3}{2}N+1
\end{align}
%
となる．$N$が大きい場合，$N^2/2$が支配的で$N^2$に比例して，計算量が増加する．このような場合，計算量のオーダーを表す記号として$O(N^2)$と書くのは，以前述べたとおりである．
%---------------------------------------------------------------------
\subsection{単純挿入ソートの様子}
%---------------------------------------------------------------------
教科書のプログラム(List 1-7)を使った場合の単純挿入ソートの様子を図\ref{fig:simple_sort}に示す．ただし，教科書とは異なり，数列(配列)の大きさは$N=20$としている．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.65]
  {figure/simple_sort.eps}
  \caption{単純挿入ソートの様子．}
  \label{fig:simple_sort}
 \end{center}
\end{figure}
%
%=====================================================================
\section{2分挿入ソート}
%=====================================================================
%---------------------------------------------------------------------
\subsection{原理}
%---------------------------------------------------------------------
これも，教科書に分かりやすく原理が書かれているので，それを使って説明する．説明するまでもなく，教科書を一読すれば，これも直ちに理解できるであろう．

計算量のオーダーに関しては，教科書の説明は不十分である．先ほどと同様に，左から$i$個，整列が完了して，$i+1$個目を整列させることを考える．
\begin{itemize}
\item 数列の$n+1$番目が挿入されるべき位置を見つけるための比較の平均回数(期待値)は，$\log_2 i$である．
\item 位置が見つかった場合，それを挿入するために，配列は平均で$i/2$の交換が必要である．
\end{itemize}
このことから，数列の$i+1$番目を正しい位置に挿入するためには，合わせて$i/2+\log_2 i$回の計算が必要となる．大きさが$N$の数列全体では，
%
\begin{align}
  \sum_{i=1}^{N-1}\left(\frac{i}{2}+\log_2 i\right)&=\frac{(N-1)(N-2)}{4}+\log_2(N-1)!\nonumber\\  
  &\qquad\text{$N$が大きい場合のスターリングの近似(} n!\simeq\sqrt{2\pi n}n^n e^{-n} \text{)を使うと}\nonumber \\
  &\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2}+\log_2\left[
  \sqrt{2\pi (n-1)}(n-1)^{(n-1)} e^{-n+1}
  \right]\nonumber \\
  &\simeq\frac{1}{4}N^2-\frac{3}{4}N+\frac{1}{2}
  +\frac{1}{2}\log_2\left[2\pi (n-1)\right]
  +(n-1)\log_2(n-1)
  +(1-n)\log_2 e
\end{align}
%
となる．$N$が大きい場合，$N^2/4$が支配的で$N^2$に比例して，計算量が増加する．従って，計算量のオーダーは，$O(N^2)$である．

これまでの計算から，2分挿入ソートは，単純挿入ソートに比べて，2倍程度の速度の増加であることが分かる．
%
%---------------------------------------------------------------------
\subsection{2分挿入ソートの様子}
%---------------------------------------------------------------------
教科書のプログラム(List 1-8)を使った場合の2分挿入ソートの様子を図\ref{fig:nibunsonyu_sort}に示す．ただし，教科書とは異なり，数列(配列)の大きさは$N=20$としている．
%
\begin{figure}[H]
  \begin{center}
    \includegraphics[keepaspectratio,scale=0.65]
		    {figure/nibunsonyu_sort.eps}
		    \caption{2分挿入ソートの様子．}
		    \label{fig:nibunsonyu_sort}
  \end{center}
\end{figure}
%
%=====================================================================
\section{ソートのまとめ}
%=====================================================================
コンピューターでは，大量のデータを取り扱う．その場合，データが規則どおりに並んでいることが重要である．規則どおりに並んでいると，データを探す時間を大幅に短縮できる．これは，人間が図書館であるタイトルの本を探すときや，英和辞典で単語を調べるときと同じである．

規則どおりにデータを並べることをソート(sort)\footnote{ソーティング，並べ替え，順序付けと言うこともある．}という．ここでは，整数のデータを小さい順(昇順)に並べる方法を学習した．ここでは述べなかったが，逆に大きい順のことを降順と言う．講義では，以下のソートについて学習した．
\begin{itemize}
\item バブルソート
  \begin{quote}
    数列の隣どうしの要素の大小を比較してそれらを交換しながらソートする方法である。交換が1回も生じなかったら，ソートが完了である．これは，小さい値のデータが泡(バブル；bubble)のように浮かんで行くように見える\footnote{昇順にソートする場合．}ことからこの名前がつけられた。
  \end{quote}
\item クイックソート
  \begin{quote}
    ある一つの要素を基準とし基準値より大きいグループと小さいグループに分ける．分けられたグループも同様の方法で分ける．全てのグループの要素が1つになるまでこの作業を繰りかえし，このときソートが完了する．いろいろなソートの中で，平均的には最速であるから，この名前がついている．
  \end{quote}
\item マージソート
  \begin{quote}
    最初に少ない個数の数列を並べ替えたグループを作る．次に、2つのグループを併合(マージ)して，より大きな並び替えられたグループを作る．これを繰り返すことにより，大きなグループができ，最終的には一つのグループになり並び替えが終了する．
  \end{quote}
\item コームソート
  \begin{quote}
    バブルソートは隣との比較のため，小さい値は一つずつしか移動できない(昇順)．比較する間隔を広くして，一気に移動させる方法がコームソートである．このソートでは，適当な間隔でバブルソートを行い徐々にその間隔を狭める方法がとられる．実験から，間隔は$1/1.3$ずつ小さくしていくのが良いと言われている．最終的には隣との比較(間隔が1)を行い，交換が起こらなければソートの完了である． 
  \end{quote}
\item 単純挿入ソート
  \begin{quote}
    まず，最初の数列の2つを比較して，小さいほうを左に，大きいほうを右にする．次に数列の3番目を，その左にある2つの数列と小さいほうから順に比較し，収まる位置を探索して，挿入する．これを，4番目,5番目，$\cdots$と順次，数列の最後まで繰り返す．最後の数列が挿入されたらソートが完了である．
  \end{quote}
\item 2分挿入ソート
  \begin{quote}
    単純挿入ソートでは，数列のある値を挿入する適当な位置は端から順に探している(リニアーサーチ)，位置を探す数列は並べ替えられているので，真中の値から比較するバイナリーサーチが可能で，それを適用して速度の向上を図った方法が，2分挿入ソートである．
  \end{quote}
\end{itemize}

これら学習したソートの計算量と安定性については，表\ref{table:sort_characteristic}(教科書の Table 1-2)のとおりである．
\begin{table}[H]
  \caption{ソートのアルゴリズムの特徴}
  \label{table:sort_characteristic}
  \begin{center}
    \begin{tabular}{lll}
      \hline
      \multicolumn{1}{c}{アルゴリズム} &
      \multicolumn{1}{c}{計算量オーダー} &
      \multicolumn{1}{c}{安定性} \\
      \hline \hline
      バブルソート & $O(N^2)$ & 安定 \\
      クイックソート &$O(N\log N)$ 〜$O(N^2)$ & 不安定 \\
      マージソート & $O(N\log N)$ & 安定 \\
      コームソート & $O(N\log N)$ & 不安定 \\
      単純挿入ソート & $O(N^2)$ & 安定 \\
      2分挿入ソート & $O(N^2)$ & 安定 \\
      \hline
    \end{tabular}
  \end{center}
\end{table}
%=====================================================================
\section{課題}
%=====================================================================
%---------------------------------------------------------------------
\subsection{課題内容}
%---------------------------------------------------------------------
以下の数列のソートに関する問題である．これをそれぞれにソートで並び替えを行った場
合，その様子を示せ．この講義ノートの「ソートの様子」で示したように記述すれば良い．
ただし，様子は手書きで書くこと．
%
\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]2分挿入ソートで昇順の場合
 \end{itemize}
\end{quote}
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は、次の通りとする。
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 11月14日(月) AM 10:40 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\
       & \qquad 授業科目名「情報工学」\\
       & \qquad 課題名「課題　ソート(その4)」\\
       & \qquad 2E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%=====================================================================
\end{document}