Version 13.10
文字列のソート
「前回は、バブルソートを実際に実装してみました」
『思ったより難しくなかったよーな』
「でも自分で１から作るときっと大変だと思うよ」
『う”……』
「さて、前回の最後に、ソートの機能のバリエーションには次のようなもの
があるって紹介しました」
・配列かそれ以外か。
・各要素の型。
・比較方法。
『前回は最後の〈比較方法〉を変えてみたりしたんだね』
「そう。ということで、今回は」
・各要素の型。
「について見てみます」
『型を変えるって、たとえば int を double にとか？』
「そういう変化だと、特に大きな違いはないかな。 > で簡単に比較できる
しね」
『文字列は？』
「そうだね、文字列のソートが例としてはいいかも。たとえば、文字列の配
列をソートする場合」
void Use_DoBubbleSortToString()
{
const char *ppchAry[5];
ppchAry[0] = "CCC";
ppchAry[1] = "BBB";
ppchAry[2] = "AAA";
ppchAry[3] = "EEE";
ppchAry[4] = "DDD";
// ソートします。
DoBubbleSortToString( ppchAry, 5 );
for( int iF1 = 0; iF1 < 5; ++iF1 )
{
TRACE( "%s ", ppchAry[iF1] );
}
TRACE( "\n" );
}
「 DoBubbleSortToString() はこれから作る関数だから」
『ソートする関数本体ってことね。文字列の配列ってこうするんだ……』
「この辺はちょっと難しいかもね。文字列ポインタは const char * だか
ら」
『その配列、ってことね』
「じゃ、次はソート本体」
// 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 DoBubbleSortToString( const char **p_ppchAry, int p_iSize )
{
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// 最後から先頭方向へのループです。
// ただし「入れ替え先」までです。
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
{
if( CompareTo( p_ppchAry[iIn - 1], p_ppchAry[iIn] )
== true )
{
// 前の方が大きいので入れ替えます。
const char *pchTemp = p_ppchAry[iIn];
p_ppchAry[iIn] = p_ppchAry[iIn - 1];
p_ppchAry[iIn - 1] = pchTemp;
}
}
}
}
「まずソート本体、 DoBubbleSortToString() から。注意点は４つ」
void DoBubbleSortToString( const char **p_ppchAry, int p_iSize )
「まずこの引数」
『ポインタのポインタだ……』
「難しく考えない方がいいかも」
const char *ppchAry[5];
「これは配列だから、 [] を取ると？」
『ポインタになる、だから const char ** ってことね』
「そういうこと。次に、ループ部分」
// 「入れ替え先」のループです。
for( int iOut = 0; iOut < p_iSize - 1; iOut++ )
{
// 最後から先頭方向へのループです。
// ただし「入れ替え先」までです。
for( int iIn = p_iSize - 1; iOut < iIn; iIn-- )
{
「ここはまったく変えてません」
『そういえば Version 13.09 ( No.245 ) でそういってたね』
「このループ部分は、バブルソートのアルゴリズム本体。ここを変えるとバ
ブルソートじゃなくなるし、バブルソートならここは固定」
『そーゆーもんなんだね』
「次は比較関数」
if( CompareTo( p_ppchAry[iIn - 1], p_ppchAry[iIn] )
「バブルソートのアルゴリズムは固定なので、比較関数のコントラクトも固
定にする必要があります」
『左の方が大きかったら true を返す、ってわけね』
「そういうこと。実際の比較関数はこんな感じ」
// 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;
}
『 strcmp() って初見だけど、ランタイム？』
「そう、文字列比較をしてくれるランタイム関数。 strcmp() は第１引数の
方が小さいとマイナス、逆に大きいとプラス、同じなら 0 の数字が返りま
す」
『数字？』
「そう、数字。この数字は特に決まってないから〈マイナス〉ってことで
チェックするようにしてください」
『はーい』
「それと、今回は英数字しか考えないけど、それ以外の文字が混ざると面倒
な話になるから」
『え、そうなの？』
「一番簡単な話が、漢字」
『あー、そういえばソートできないよね……』
「この〈比較〉っていうのは、実はかなり複雑。構造体を使って複数のデー
タを比較したり、計算が絡んだりするとさらに複雑になるから」
『難しそう……』
「最後に、入れ替え箇所」
// 前の方が大きいので入れ替えます。
const char *pchTemp = p_ppchAry[iIn];
p_ppchAry[iIn] = p_ppchAry[iIn - 1];
p_ppchAry[iIn - 1] = pchTemp;
『つか普通じゃない、別になんか特別なことある？』
「あるよ」
const char *pchTemp = p_ppchAry[iIn];
「この pchTemp には何が入ってる？」
『文字列』
「正確に言うと？」
『文字列のポインタつかアドレス……あ、アドレスを入れてるだけ……』
「そういうこと。ここでの入れ替えは、ポインタを入れ替えてるだけ。文字
列そのものはコピーとか全然してません」
『そういえば……』
「この文字列もそうだし、構造体をソートするときもそうだけど、この入れ
替え部分は〈まとめてコピー〉とかすると大変だから、ポインタで持って、
そのポインタだけを入れ替えます」
『文字列のコピーだと大変だよね。ってゆーか、サイズ違うんだから
malloc() で再確保、ってゆーか CString 使った方がいいのかな？』
「そうだね。次の次の回で説明するけど、 CString を使う時には配列じゃ
ない、便利なクラスがあるからそれを使うのがいいかな」
『へー』
「文字列の配列っていうのはよく使うからね。話を戻して、基本的にこうい
う場合にはポインタだけ入れ替えます」
『コピーは大変だもんね。でも〈こういうとき〉って？』
「普通の変数だけの配列じゃなかったら、ポインタの方が楽かも。ソートは
それができるし」
『どういうこと？』
「前に言ったでしょ、ソートは単に入れ替えるだけだから、要素が増えたり
減ったりしないんです」
『 new したり delete したり、ってことを考えなくていい』
「そういうこと。だから、ソートの時にはポインタの配列が普通、って思っ
た方がいいかも」
/*
Preview Next Story!
*/
『基本的にはこれまでと同じよね』
「ソートの機能そのものは変わらないからね」
『構造体とかクラスになるとやっぱ大変？』
「どの変数でソートするかとか、安定ソートとか色々とね」
『というわけで次回』
＜ Version 13.11 構造体のソート ＞
「につづく！」
『構造体も < とかで簡単に比較できたらいいのに』
「そういう方法もあるよ」
『え！？』
「教えるのはまだ先だけどね……」
users
users
