Version 13.06
アルゴリズムの定番・ソート

「これからアルゴリズムの作り方について説明するけど、まずはわかりやす
い例から、ってことでソートについて説明します」
『ソートって並べ替えってことだよね』
「そう、たとえば」

5
2
7
1

「って並んでいるものを」

1
2
5
7

「って並べ替えること」
『逆順っていうのもあるんじゃない？』
「そうそう。専門用語で【昇順】と【降順】って言います」
『しょうじゅん、こうじゅん、ね』

・昇順
1
2
5
7

・降順
7
5
2
1

「重要なのは、これは〈並べる方向に対して、増えていくなら昇順、減って
いくなら降順〉ってこと」
『どゆこと？』
「【昇】って付いていても、方向は表さないってこと。もし【昇る】って意
味なら上の降順の例の方が昇順って勘違いするんじゃないかなと思って」
『……んなの言われなきゃ思わないよ』
「え”」
『なんか言われたらすごくややこしくなった……』
「あ−、まぁ、増えていくのが昇順、減っていくのが降順、ってことで」
『はいはい』
「ソートはアルゴリズムの中でも比較的簡単なもの。一番楽なのは、データ
の増減がないってことかな」
『並び替えだから減ったり増えたりしないわけね』
「もしこれが増えたりすると、配列では実現できないから」
『めんどくさくなっちゃうね……』
「そういう点で簡単、っていうのや、よく使うものだから、最初にしておく
と楽かな」
『はーい』
「ソートのアルゴリズムを考える上で重要なポイントは、次の５つ」

・配列かそれ以外か。
・各要素の型。
・比較方法。
・ソートの早さ。
・安定かどうか。

「まず〈配列かそれ以外か〉について。普通は配列なんだけど、配列以外の
場合もあるから」
『配列以外？』
「配列って、サイズの変更ができないでしょ」
『そだね、 Version 11.15 ( No.215 ) で教わったけど、大変だったもん
ね』
「その大変な、サイズの変更とかを自動的にしてくれるクラスがあるんで
す。 MFC だと CArray 、標準 C++ ライブラリだと std::vector とか」
『つまり配列の代わりにそういうのも使える、ってことね』
「そういうこと。ソートはサイズの拡張は必要ないから配列でいいんだけ
ど、こういう他のも使う可能性があるからその辺も見ておきます」
『はーい。次の〈各要素の型〉ってそのまんまね』
「でも、それ以上の意味があるんです」
『え？』
「一番重要な問題は、ポインタにするかしないか。ソートって、さっきみた
いなただ数字が並んでいるものをソートするよりも、構造体をソートする方
が多いんです」
『その方が多そうだね』
「で、ソートするってことは〈各要素を入れ替える〉ってことだから」
『そか、順番並び替えるわけだから……構造体そのまま入れ替えたら大変、
だからポインタの方が早い、ってこと？』
「そういうこと。ただ、ポインタを使う場合、動的に構造体を作る必要が
あるから」
『ちょっと面倒そうね』
「現実的にはポインタを使わないと大変だから、ポインタを使用した場合の
説明を中心にします」
『次の〈比較方法〉は Version 13.01 ( No.237 ) の時のだよね』
「そう、構造体で比較する時にはどの変数で比較するのか、っていうのが問
題になります。それに、この比較部分をちょっと間違えるとソート結果が大
きく変わるから、とても重要」
『順番決めるだけなんだからそんな大変そうに見えないけど』
「単純な比較ならそうなんだけど……。次の〈ソートの早さ〉も、さっきの
13.01 で話したこと」
『方法によってかかる時間がかなり変わる、ってことね』
「ソートのアルゴリズム、っていうとこの部分が一番重要かな。僕としては
それほど重要視してないんだけど……」
『でも早さは重要じゃない？』
「それはそうなんだけど……」
『最後の〈安定かどうか〉って？　アルゴリズムって、何度やっても結果は
同じなんじゃないの？』
「もちろんそう。この【安定】っていうのは別の意味。たとえば……」

1-5
4-7
2-3
4-3

「っていうデータがあるとします。これを、まず右側の数字でソートしま
す」

2-3
4-3
1-5
4-7

「で、重要なのは、次に左側の数字でソートした場合の話。どうなると思
う？」
『って、普通に考えれば』

1-5
2-3
4-3
4-7

『でしょ？』
「ところが、そうならずに」

1-5
2-3
4-7
4-3

「ってなる場合もあります」
『最後が逆だ……』
「２回目のソートは〈左側の数字〉しか見ないから、右側の数字の順番につ
いてはまったく見ないんです」
『でも前の順番ってそのまま残さないの？』
「そこがポイント。その〈前の順番を残すソート〉を【安定ソート】とか
【ステーブルソート】って言います」
『あ……ってことは、普通のソートは前の順番を残さないの？』
「残す物もあるし残さない物もある、かな。何も書かれてなくても安定ソー
トのものもあるから。でも、安定ソートっていうのは重要だから、普通は
ちゃんと書かれていると思うよ」
『ってゆーか、普通安定ソート使うんじゃない？』
「そうとも限らなくて、実は、早さを追求すると【安定ソート】にならない
んです」
『え』
「ソートのための最適化でまぜこぜにしちゃうから、前の順番が残らないん
です。その分早いわけだけど」
『早さか安定、か』
「それだけでもないよ。たとえば、さっきの例だけど、比較方法を次のよう
に定義したら？」

・左の数字が小さい順に並び替える。
　左の数字が同じものは右の数字が小さい順に並び替える

『あ、これだとちゃんと並ぶね』
「これが許されるんであれば、早さ重視でもいいでしょ」
『許されない場合ってあるの？』
「リスト表示とかで、使ってるひとが何度でもソートできるようにする場合
とかは無理。〈これまでにしたソート〉の履歴を取っておかないといけない
から」
『んー、それってエクスプローラーとか？』
「エクスプローラーは違うよ。検索してから、ファイル名で降順でソートし
て、フォルダでソートし直すと」
『げ、ファイル名が昇順で並んでる……』
「だからこれは例にならないけどね。あと、早さの問題も簡単には解決しな
いかな。まず、２回ソートするよりも１回で２項目まとめてソートした方が
早くなります」
『そなの？』
「全体を見る量が減るし、安定ソートを使う必要がないから」
『早いソートを使えるわけね』
「でも、エクスプローラーとかだと、毎回全項目でソートするよりは、前に
検索したものを使って安定ソートを１回する方が早いことが多いです」
『そか、ソート済みのを利用すれば、それだけ早くなる……』
「以上を踏まえて、もう一度この一覧を見てみて」

・配列かそれ以外か。
・各要素の型。
・比較方法。
・ソートの早さ。
・安定かどうか。

「たとえば、比較方法。エクスプローラーだと色々な形式で比較する必要が
あるでしょ。ファイル名、ファイルサイズ、日付、などなど」
『面倒そう……って、それってそれぞれ別の比較方法にしなきゃいけないっ
てこと？』
「そういうこと。だから、エクスプローラーのソートだと比較方法を自由に
変えられないといけないんです。降順にする必要もあるしね」
『そういえば……』
「ソートは、必要条件でどういうものにしなきゃいけないのか考える必要が
あるんです」
『だから結構複雑……』
「でも、だからと言ってソートを１から作るのは大変だから、元々あるもの
の流用のしかたや、自分が作ったものを流用しやすくする方法も絡めつつ、
ソートの仕組みについて説明していきます」

/*
    Preview Next Story!
*/
『……なんかちょっと大がかり？』
「〈アルゴリズムでソート〉って言ったら、すごくメジャーだから」
『そなの？』
「本とかで一章まるまる使うくらいだからね」
『というわけで次回』
＜ Version 13.07 最も簡単なソート ＞
「につづく！」
『つか、じゃあアルゴリズム編ってやたら長くなるんじゃない？』
「違うよ火美ちゃん」
『え？』
「〈も〉だよ」