ソート

• ヒープソート

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

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

		
public static SortResult Heap( int[] nDats )
{
	SortResult result = new SortResult( "Heap" );
	result.LogicCompCount = HeapComparison( nDats.Length );
	result.CompCountLogic = "n log2( n )";

	// 必要なヒープ用配列を確保します
	int[] nHeaps = new int[ nDats.Length ];
	int nNum = 0;
	int i = 0;

	// ヒープに要素を追加します
	for( i = 0; i < nDats.Length; i++ )
	{
		InsertToHeap( nHeaps, ref nNum, nDats[ i ] );
	}
	// ヒープから取り出しながら配列に格納します。
	for( i = 0; nNum > 0; i++ )
	{
		nDats[ i ] = FetchTopNode( nHeaps, ref nNum );
	}

	result.End();
	return result;
}

private static void InsertToHeap( int[] nHeaps, ref int nNum, int nDat )
{
	nHeaps[ nNum++ ] = nDat;

	int i = nNum;
	int j = i / 2;
	while( i > 1 && nHeaps[ i - 1 ] < nHeaps[ j - 1 ] )
	{
		int t = nHeaps[ i - 1 ];
		nHeaps[ i - 1 ] = nHeaps[ j - 1 ];
		nHeaps[ j - 1 ] = t;
		i = j;
		j = i / 2;
	}
}

/*
 * 先頭の要素を取り除き、返す
 */
private static int FetchTopNode( int[] nHeaps, ref int nNum )
{
	int r = nHeaps[ 0 ];
	nNum--;
	nHeaps[ 0 ] = nHeaps[ nNum ];
	int i = 1;
	int j = i * 2;
	while( j <= nNum )
	{
		if( j + 1 <= nNum && nHeaps[ j - 1 ] > nHeaps[ j ] )
		{
			j++;
		}
		if( nHeaps[ i - 1 ] > nHeaps[ j - 1 ] )
		{
			int t = nHeaps[ i - 1 ];
			nHeaps[ i - 1 ] = nHeaps[ j - 1 ];
			nHeaps[ j - 1 ] = t;
		}
		i = j;
		j = i * 2;
	}
	return r;
}