Version 13.11
構造体のソート
「前回は文字列のソートをしてみました。今回は構造体のソートをしてみま
す」
『ちょっと面倒そう……』
「面倒って言うほど面倒じゃないと思うよ。ただ、プログラム自体はちょっ
と長くなるけど」
『げ』
「というわけで、まずはそのプログラムから」
// 配列の要素にする構造体。
struct SORT_DATA
{
int m_iIndex;
CString m_cDataStr;
};
// p_iL > p_iR なら true を、
// それ以外は false を返すようにしてください。
bool CompareTo( int p_iL, int p_iR )
{
if( p_iL > p_iR )
{
return true;
}
return false;
}
// p_pchL > p_pchR なら true を、
// それ以外は false を返すようにしてください。
bool CompareTo( const char *p_pchL, const char *p_pchR )
{
if( strcmp( p_pchL, p_pchR ) > 0 )
{
return true;
}
return false;
}
// ソート本体。
void DoBubbleSortToStruct( SORT_DATA **p_ppstAry, int p_iSize )
{
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// 最後から先頭方向へのループです。
// ただし「入れ替え先」までです。
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
{
if( CompareTo
( p_ppstAry[iIn - 1]->m_iIndex
, p_ppstAry[iIn]->m_iIndex
)
== true )
{
// 前の方が大きいので入れ替えます。
SORT_DATA *pstTemp = p_ppstAry[iIn];
p_ppstAry[iIn] = p_ppstAry[iIn - 1];
p_ppstAry[iIn - 1] = pstTemp;
}
}
}
}
『長！ ……あれ？ そうでもない？ 最初のは構造体だし、 CompareTo()
はなぜか２個あるし』
「それと、使用例はこんな感じ」
void Use_DoBubbleSortToStruct()
{
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";
// ソートします。
DoBubbleSortToStruct( 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];
}
}
『構造体の配列……じゃないね、構造体のポインタの配列？』
「そう。前回説明したように、入れ替えるためにもポインタで持っておいた
方がいいから」
『それぞれの構造体は new して作ってるんだね』
「 new については Version 11.12 ( No.212 ) を参照。ポインタで持つた
めに、 new で動的に作ります。前回の文字列も、実際にはこういうふうに
動的に作ることになると思うよ」
『だよね、配列の数とか、今は５個固定だけど、ホントに使う時には変わる
だろうから……』
「その辺については次回説明する【コレクション】が解決してくれるかな」
『これくしょん？』
「これは次回のお楽しみということで、まずは今回のソートについて」
『まず引数』
void DoBubbleSortToStruct( SORT_DATA **p_ppstAry, int p_iSize )
「ポインタの配列だから、ポインタのポインタになります」
『これは文字列の時と一緒ね』
「次のアルゴリズムの部分、は」
『何があっても変わらない！』
「そういうこと。配列の要素が構造体になっても、ここは同じ」
『次は比較部分ね』
if( CompareTo
( p_ppstAry[iIn - 1]->m_iIndex
, p_ppstAry[iIn]->m_iIndex
)
== true )
『あれ？ CompareTo() ってふたつあるけど、どっち呼ばれてる？』
「引数に m_iIndex 、つまり int の変数を渡しているから」
『 bool CompareTo( int p_iL, int p_iR ) って方だね。これって
オーバーロードってやつ？』
「そう。 Version 11.19 ( No.219 ) で説明した、同じ名前の関数を、引数
の型を変えれば複数作れるっていうの」
『で、この例だと int で比較してる、と』
「それはつまり」
struct SORT_DATA
{
int m_iIndex;
CString m_cDataStr;
};
「だと、 m_iIndex でしかソートされないってこと」
『あ…… m_cDataStr は無視？』
「そういうこと。だから、この結果はこうなります」
1, CCC
3, DDD
3, BBB
5, AAA
9, EEE
『文字列全く無視……』
「この比較部分を」
if( CompareTo
( p_ppstAry[iIn - 1]->m_cDataStr
, p_ppstAry[iIn]->m_cDataStr
)
== true )
『あ、文字列で比較してる』
「こうなります」
5, AAA
3, BBB
1, CCC
3, DDD
9, EEE
『おー、 m_cDataStr の方でソートされた！』
「今はプログラムを変えることで対応したけど、場合によっては、どっちで
ソートするっていうのは動的に変えられた方がいいこともあります」
『ファイルのソートとかはそうってことね』
「そういうこと。それに、まず m_iIndex でソートして、次に m_cDataStr
でソートする、っていうこともしたい場合もあるでしょ」
『そっか、そういうソートもあるね』
「そういう場合には構造体まるごと引数として渡さなきゃいけないかな。他
にも降順にソートしたい場合とか、この辺は必要に応じて手を加える必要が
あるかな」
『あ……今ので思い出したんだけど、これってちゃんと安定ソートしてる
ね』
「そう、そこも重要。構造体は比較するデータの他にもデータがあるわけだ
から、安定ソートかそうでないかは重要。 Version 13.08 ( No.244 ) で説
明したように」
if( p_iL >= p_iR )
「ってすると、安定ソートじゃなくなります」
1, CCC
3, BBB
3, DDD
5, AAA
9, EEE
『 3 の位置が変わってる……』
「この比較部分はかなり重要な箇所だから注意してコーディングしてくださ
い」
『コードの量は多くないのにね』
/*
Preview Next Story!
*/
『結構注意点多いよね』
「簡単そうに見えるところでも、押さえておくべき点があるってことかな」
『ま、そういうの教わるために教えてもらってるんだけど』
「次回のコレクションもそういうの多いです」
『げ』
「というわけで次回」
＜ Version 13.12 コレクションを使ってみよう ＞
『につづく！』
「げ、って教わるために教えてるんだけど」
『それはそれ、これはこれ』
users
users
