26.1.6.26 整列の効率化

最小値から順々に決めてゆくSort1のやり方は，実はあまり能率のいい方法ではありません．その最大の理由は，例えば最初に全体の最小値を求める処理の中で行なった比較の結果をほとんど全部無駄に捨ててしまうからです．最初の配列が

34, 28, 84, 91, 16, 57, 49, 70, 19, 63

である場合，この中の最小値を求めるために行なわれた比較は

34:28, 28:84, 28:91, 28:16, 16:57, 16:49, 16:70, 16:19, 16:63

の9通りです．その結果16が最小値であることがわかり，次の配列が

16, 28, 84, 91, 34, 57, 49, 70, 19, 63

となりますが，次の段階で行なわれる比較は

28:84, 28:91, 28:34, 28:57, 28:49, 28:70, 28:19, 19:63

の8通りです．このうちでこの色で示される3通りの比較は，最初の回ですでに行なわれているので，無駄な操作と言うことができます．

このような無駄をできるだけ省くためには，同じ比較を繰り返さないように，できるだけ要素を分割して扱うようにします．整列のアルゴリズムは数多く研究されていますが，ここでは代表的である2例を説明します．

第1の方法は併合整列(マージソート，merge sort)と呼ばれる方法で，おおまかに言うと，部分的に整列している2つの並びの中の要素を，頭から順に比較してゆき，結果として全体を整列するやり方です．この方法では，同じ要素同志の比較が2回以上行なわれることは決してありません．

第2の方法は交換分割整列で，単純なアルゴリズムである割には平均的には非常に速いので，クイックソート(quick sort)と呼ばれる方法です．この方法では，配列をおおまかに整列し，そのおおまかさを次第に細かくしてゆきます．