26.1.6.21 整列の基礎

探索のところでも触れましたが，データが大きさの順番に並んでいるといろいろな処理の効率を上げることができます．それで，最初は順番どおりには並んでいないデータを，値の順番に並べ直すことが重要となります．この処理を一般に整列あるいはソート(sort)と呼びます．

整列の基本的な操作は，要素値の交換です．最終的に大きさの小さい順に並べるものとすると，ある2つの要素が大きさの逆順になっていたら，それを交換した方が最終状態に近ずきます．たとえば

13, 75, 36, 51, 40, 80

と並んでいるとき，75と40とを交換した方がより整列した状態になります．

13, 40, 36, 51, 75, 80

ここで，データの個数をn個とするとき，その中から2個を選ぶやり方の数はn(n-1)/2通りですから，これだけの回数検査して(必要なら)交換すれば整列は完了します．

交換する要素はどのように選んだらいいでしょうか．交換するたびに要素の場所は変ってしまいますから，いいかげんに場所を頼りにすると正しい交換ができません．そうかと言って，交換した要素すべてを追跡してゆくのもかなりの手間です．実際のアルゴリズムとしては，このどちらかについて巧妙に無駄を省くやり方が使われます．

たとえば，最も左の位置を考えると，ここに最終的に来るべき要素は全体の最小値であることは明らかです．それで，最小値を求めるための一般的なやり方(順々に2つずつ比較し，小さい方を残してゆく)をやって，求まった最小値(の要素)と最も左にある要素とを交換すれば，整列状態へ一歩近づきます．