※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
(4)クイックソート

  昔からなぜか人気のあるソートである。データを「適当に」決めた基準値
  を元に大きい物と小さい物とに２分割し、その分割されたものを更に２分
  割する、ということを繰り返してソートする。

　コーディングが単純で実装しやすいが、重大な欠陥がある。それについて
　は実行時間の掲示後に書く。

【Coding Sample】(Quick Sort)

void CSortDlg::QuickSort()
{
	QuickSort(0, m_dcnt-1);
}
void CSortDlg::QuickSort(long n1, long n2)
{
	long i,j;
	long m,x;

	if (n2<=n1)
		return;

	m = m_data[n1];
	i = n1+1;
	j = n2;
	while(i<j)
	{
		if (m_data[i]<m)
		{
			if (m<=m_data[j])	// i<m<j : iは小、jは大
			{
				i++;
				j--;
			}
			else	//i,j<m : 両方とも小
			{
				x = m_data[i+1];
				m_data[i+1] = m_data[j];
				m_data[j] = x;
				i+=2;
			}
		}
		else
		{
			if (m<=m_data[j])	// m<i,j : i,jともに大
			{
				x = m_data[j-1];
				m_data[j-1] = m_data[i];
				m_data[i] = x;
				j-=2;
			}
			else	// j<m<i : jは小,iは大
			{
				x = m_data[j];
				m_data[j] = m_data[i];
				m_data[i] = x;
				i++;
				j--;
			}
		}
	}
	if (i==j)
	{
		if (m<=m_data[i])
			j--;
		else
			i++;
	}
	//ここで n1+1〜jはm未満, i〜n2はm以上になっている (j+1=i)

	if (j==n1)	//全てm以上だった
	{
		QuickSort(i,n2);
	}
	else	//m未満のものがある
	{
		x = m_data[j];
		m_data[j] = m_data[n1];
		m_data[n1] = x;

		QuickSort(n1,j-1);
		QuickSort(i,n2);
	}
	
}


【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　             件数　   乱順　　　　正順　　　　逆順

QuickSort(r)      100    0.00000     0.00000     0.00000
QuickSort(r)     1000    0.00000     0.00000     0.00000
QuickSort(r)    10000    0.00000     0.16000     1.71000
QuickSort(r)    30000    0.11000     0.93000    10.98000
QuickSort(r)   100000    0.33000     4.94000    64.70000
QuickSort(r)   300000    1.04000    31.52000   684.32000
QuickSort(r)  1000000    4.72000   209.98000    -------
QuickSort(r)  3000000   24.12000    -------     -------

　QuickSortはご覧の通り、順序に並んだデータに極端に弱い。つまり、正順
　・逆順などに並んだデータにおいては分割が「１個とその他」にしか分かれ
　てくれないので、王様探し並みに速度が落ちてしまうのである。

　また、このソートは他のソートと違って、First in First out ではないの
　で、入力順を保ちたければ、入力順もキーに加えておく必要がある。