%=====================================================================
% ���Ĺ��� 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}
