ソート

• クイックソート

クイックソートのアルゴリズムをC#で実装しています。アルゴリズムの解説は省略します。

ソースの全貌はこちらよりダウンロードしてください。

		
public static SortResult Quick( int[] nDats )
{
	SortResult result = new SortResult( "Quick" );

	QuickSortRecursive( nDats, 0, nDats.Length - 1, result );

	return result;
}
private static void QuickSortRecursive( int[] nDats, int i, int j, SortResult result )
{
	if( i == j ) return;
	int nPivot = GetPivot( nDats, i, j );
	if( nPivot != -1 )
	{
		int nMiddle;
		Partitionize( nDats, i, j, nPivot, out nMiddle, result );
		QuickSortRecursive( nDats, i, nMiddle - 1, result );
		QuickSortRecursive( nDats, nMiddle, j, result );
	}
	return;
}
/// <summary>
/// パーティション分割。a[i]〜a[j]の間で、x を軸として分割します。
/// x より小さい要素は前に、大きい要素はうしろに来ます。
/// 大きい要素の開始番号を返します。
/// </summary>
/// <param name="nDats">データ</param>
/// <param name="i">検索開始位置</param>
/// <param name="j">検索終了位置</param>
/// <param name="nPivot">ピボット</param>
/// <param name="nMiddle">大きい要素の開始番号</param>
/// <param name="result">ソート結果</param>
private static void Partitionize( int[] nDats, int i, int j, int nPivot, out int nMiddle, SortResult result )
{
	int n = i;
	int m = j;

	// 検索が交差するまで繰り返します
	while( n <= m )
	{
		// 軸要素以上のデータを探します
		//	while( n <= j && nDats[ n ] < nPivot )
		while( n <= j && nDats[ n ] < nDats[ nPivot ] )
		{
			result.CompCount++;
			n++;
		}
		// 軸要素未満のデータを探します
		//	while( m >= i && nDats[ m ] >= nPivot )
		while( m >= i && nDats[ m ] >= nDats[ nPivot ] )
		{
			result.CompCount++;
			m--;
		}
		if( n > m ) break;

		result.SwapCount++;

		// スワップ
		Swap( ref nDats[ n ], ref nDats[ m ] );

		// ピボットの値を取得するインデックスも移動
		if( nPivot == n ) nPivot = m;
		else if( nPivot == m ) nPivot = n;

		n++;
		m--;
	}
	nMiddle = n;
}
/// <summary>
/// 軸要素の選択。順に見て、最初に見つかった異なる2つの要素のうち、
/// 大きいほうのインデックスを返す。全部同じ要素の場合は -1 を返す。
/// データの先頭の要素を軸要素とする 
/// </summary>
/// <param name="nDats">データ</param>
/// <param name="i">検索開始位置</param>
/// <param name="j">検索終了位置</param>
/// <returns>ピボット</returns>
private static int GetPivot( int[] nDats, int i, int j )
{
	int k = i + 1;
	while( k <= j && nDats[ i ] == nDats[ k ] )
	{
		k++;
	}
	if( k > j ) return -1;
	if( nDats[ i ] >= nDats[ k ] ) return i;
	return k;
}