Version 13.20
マージソート・汎用版
「前回はマージソートについて説明しました」
『でもクイックソートみたいにランタイムにないのは面倒よねー』
「というわけで、汎用的に使えるマージソートを用意しました」
// 配列の要素にする構造体。
struct SORT_DATA
{
int m_iIndex;
CString m_cDataStr;
};
// 比較用関数。
// p_pL > p_pR なら true を、
// それ以外は false を返すようにしてください。
bool CompareToForSORT_DATA( void *p_pL, void *p_pR )
{
SORT_DATA *pstSortDataL = (SORT_DATA *)p_pL;
SORT_DATA *pstSortDataR = (SORT_DATA *)p_pR;
// 数値のみで比較します。
if( pstSortDataL->m_iIndex > pstSortDataR->m_iIndex )
{
return true;
}
return false;
}
void DoMergeSort( SORT_DATA **p_ppstAry, int p_iSize )
{
if( p_iSize <= 1 )
{
// 要素数が１以下なら何もしません。
return;
}
// 中央から左側のサイズを取得します。
int iLeftSize = p_iSize / 2;
// 中央から右側のサイズを取得します。
int iRightSize = p_iSize - iLeftSize;
// 中央から左側のサイズの配列を作成します。
SORT_DATA **ppstLeftAry = new SORT_DATA*[iLeftSize];
// 中央から右側のサイズの配列を作成します。
SORT_DATA **ppstRightAry = new SORT_DATA*[iRightSize];
// それぞれコピーします。
int iF1;
for( iF1 = 0; iF1 < iLeftSize; ++iF1 )
{
ppstLeftAry[iF1] = p_ppstAry[iF1];
}
for( iF1 = 0; iF1 < iRightSize; ++iF1 )
{
ppstRightAry[iF1] = p_ppstAry[iLeftSize + iF1];
}
// それぞれ再帰呼び出しします。
DoMergeSort( ppstLeftAry, iLeftSize );
DoMergeSort( ppstRightAry, iRightSize );
// マージします。
int iLeftPos = 0;
int iRightPos = 0;
while(
( iLeftPos < iLeftSize ) ||
( iRightPos < iRightSize )
)
{
// 左右両方とも配列の中にいる間、ループします。
if( iRightSize <= iRightPos )
{
// 右側が配列の最後まで来ている場合。
// 左側を追加します。
p_ppstAry[iLeftPos + iRightPos] = ppstLeftAry[iLeftPos];
++iLeftPos;
}
else if( iLeftSize <= iLeftPos )
{
// 左側が配列の最後まで来ている場合。
// 右側を追加します。
p_ppstAry[iLeftPos + iRightPos] = ppstRightAry[iRightPos];
++iRightPos;
}
else if
( CompareToForSORT_DATA
( ppstLeftAry[iLeftPos]
, ppstRightAry[iRightPos]
)
)
{
// 左側の方が右側より大きい場合。
// 右側を追加します。
p_ppstAry[iLeftPos + iRightPos] = ppstRightAry[iRightPos];
++iRightPos;
}
else
{
// それ以外の場合（左側の方が右側より小さい場合）。
// 左側を追加します。
p_ppstAry[iLeftPos + iRightPos] = ppstLeftAry[iLeftPos];
++iLeftPos;
}
}
// 解放します。
delete[] ppstLeftAry;
delete[] ppstRightAry;
}
『長い……けど、前とほとんど同じね。比較用関数が増えたくらい』
「使用例はこう」
void Use_DoMergeSort()
{
SORT_DATA *ppstAry[5];
ppstAry[0] = new SORT_DATA;
ppstAry[0]->m_iIndex = 9;
ppstAry[0]->m_cDataStr = "EEE";
ppstAry[1] = new SORT_DATA;
ppstAry[1]->m_iIndex = 3;
ppstAry[1]->m_cDataStr = "DDD";
ppstAry[2] = new SORT_DATA;
ppstAry[2]->m_iIndex = 1;
ppstAry[2]->m_cDataStr = "CCC";
ppstAry[3] = new SORT_DATA;
ppstAry[3]->m_iIndex = 3;
ppstAry[3]->m_cDataStr = "BBB";
ppstAry[4] = new SORT_DATA;
ppstAry[4]->m_iIndex = 5;
ppstAry[4]->m_cDataStr = "AAA";
// ソートします。
DoMergeSort( ppstAry, 5 );
for( int iF1 = 0; iF1 < 5; ++iF1 )
{
TRACE
( "%d, %s\n"
, ppstAry[iF1]->m_iIndex
, ppstAry[iF1]->m_cDataStr
);
// new で作ったので delete で解放します。
delete ppstAry[iF1];
}
}
「実行結果はこう」
1, CCC
3, DDD
3, BBB
5, AAA
9, EEE
『お、ちゃんと安定ソートになってる！』
「マージソートは安定ソートだから、構造体やクラスのソートに使うことが
多いと思って、今回は構造体を例にしてみました」
『でもこれって完全に汎用的、ってわけじゃないよね。 SORT_DATA のポイ
ンタのポインタが引数なんだから』
「そうだね、使う時にはちょっと修正が必要かな。でも比較用関数が」
bool CompareToForSORT_DATA( void *p_pL, void *p_pR )
『あ、 void ポインタだ』
「だから、この辺の型は気にする必要ないから。比較用関数の中身とか変え
れば何にでも使えると思うよ」
『比較用関数って、前に教わったのと同じ？』
「 Version 13.09 ( No.245 ) と同じ、左の方が大きければ true 、それ以
外は false 」
『 qsort() とは違うんだね』
「この比較用関数は、いろんなプログラムにあって、それぞれ仕様が違うか
らちょっと判りにくいかも。 qsort() の仕様に合わせるっていうのもあり
だと思うよ」
『他に違いってある？』
「他は前回と同じ。アルゴリズム自体同じだし、比較してる１箇所を比較用
関数に置き換えただけだし」
『そういえば、 qsort() みたいに void ポインタを受け取るっていうふう
にはできないの？』
「できなくはないけど、要素のサイズも渡さなきゃいけないし」
『あ、そっか』
「型が判れば、要素のサイズは渡さなくて済むからね。それに、そこまで汎
用化する必要はないかな、数カ所置き換えるだけで済むから」
『んーあと……比較用関数を引数に渡すってできる？』
「それは簡単にできるよ。まずアルゴリズムの引数を」
void DoMergeSort
( SORT_DATA **p_ppstAry, int p_iSize
, bool ( *p_pfnComparetor)( void *p_pL, void *p_pR )
)
「ってして、再帰呼び出し部分は」
// それぞれ再帰呼び出しします。
DoMergeSort( ppstLeftAry, iLeftSize, p_pfnComparetor );
DoMergeSort( ppstRightAry, iRightSize, p_pfnComparetor );
「実際に比較用関数を呼んでいる箇所は」
else if
( p_pfnComparetor
( ppstLeftAry[iLeftPos]
, ppstRightAry[iRightPos]
)
)
「ってすれば、あとは」
// ソートします。
DoMergeSort( ppstAry, 5, CompareToForSORT_DATA );
「でＯＫ」
『おー』
「このぐらい汎用化すれば、たいがいのことには使えるかな」
/*
Preview Next Story!
*/
『この汎用ソートがあれば十分って感じよねー』
「というわけでソート編は次回で最後」
『早！』
「というわけで次回」
＜ Version 13.21 ソートのまとめ ＞
『につづく！』
「でもアルゴリズム編はまだ続くからねー」
『今回ももう２０回突破……』
users
users
