Pythonプログラミング（ステップ８・ソーティング）

１．作業を小分けにしてゆく：クイックソート

ソーティングの中で、一番簡単な問題は、要素がひとつだけのリストの並べ替えで、リスト$[a]$ を並べ替えた結果は $[a]$である。

次に簡単なのは、$[a,b]$ の並べ替えで、例えば昇順に整列する場合、$a\le b$ であったら、$[a,b]$、そうでなければ $[b,a]$を結果とすれば良い。

ここで、$a,b$ がリストの場合($a=[a_1,\cdots ,a_n],b=[b_1,\cdots ,b_m]$)に、上の議論を拡張してみよう。 そして、$[a_1,\cdots ,a_n]\le [b_1,\cdots ,b_m]$とは、全ての要素のペアについて $a_i\le b_j$ が成り立つこと、と定義する。

次に、あるリスト $x=[x_1,\cdots ,x_n]$ が与えられたとき、それを、$a\le b$ であるようなふたつのリスト $a,b$ に分解する方法を考えてみよう。 集合論の記号を使えば、$a\subseteq x,b\subseteq x$ であって、かつ、共通要素が無い、つまり $a\cap b=\varnothing$ とする。 例えば、$[3,1,7,2,5]$ を $[3,1,2]$ と $[7,5]$ に分割する手順をどう与えるか、という意味である。 この定義からは、リストに同じ要素が複数含まれている場合、分割の方法は (重複する要素の数)-1 通り存在することになる。

リストを大小ふたつの部分リストに分割するには、ある参照値を決めて、それより小さいグループと大きいグループに選別すればよい。 この参照値はピボット(pivot)と呼ばれている。

ピボットの選び方は大切である。 なぜなら、もし、リスト中の最大値以上の数や最小値以下の数を選んでしまうと、片側のリストが「空」になってしまう場合が生じる。 つまり、分割したはずなのに、分割されていない、という状況が生まれてしまうからである。 実用上よく使われるのは、リストの中からいくつか要素をピックアップして、その平均値をピボットとする、という方法である。 そうすれば、よほど運が悪く無い限り、ピボットが極端な値となることは無いはずだ。

こうして、長いリスト $x$ が、$a\le b$ となるような２つのリストに分解できたとしよう。 そして、さらに $a,b$ も同様に分解して・・・という操作を繰り返していけば、いずれ、要素が1つだけのリストになる。 そのとき、その部分列の整列作業は完了し、かつ、分解されたそれぞれのリストの大小関係も、昇順に揃っているはずである（下図）。

このように、リストを、要素の値の大小によって２つのグループに分割する操作を繰り返し、全体を整列させるアルゴリズムはクイックソート（quicksort）と呼ばれ、その名のとおり、高速な整列アルゴリズムの定番である。

アルゴリズムの検証

以上のアイデアをリストを使ってそのまま表現してみたPythonコードの例を以下に示す。 ピボットの値は、リストの要素を最初から試しつつ、それより小さな値のデータをリストxsm、値の大きなデータをリストxlgに加えて、 それぞれのリストについてソーティングした結果を連結した上で、関数の値として返すようにしている。 リストの長さが1の場合は、並べ替える必要がもう無いので、リストのそのまま返す。 また、リストがふたつに分割できなかった場合は、ピボットとなる要素を順に変えながら試すようになっている。

 
def quick_sort(x):
    n = len(x)
    if n<=1:
        return x
    ip=0
    while ip<n:
        pv = x[ip]
        xsm=[ ]
        xlg=[ ]
        for i in range(n):
            if x[i] <= pv:
                xsm.append(x[i])
            else:
                xlg.append(x[i])
        if len(xsm)>0 and len(xlg)>0:
            return quick_sort(xsm) + quick_sort(xlg)
        ip=ip+1
    return x

# メイン部
X=[0.3, 1.3, 10.2, 3.3, 9.3, 7.9, 2.1, 0.1, 4.2, 8.3, 5.9, 7.7, 8.1, 2.8]
Xsorted = quick_sort(X)
print(Xsorted)  

このコードは正しく動作はするものの、関数呼び出しの都度リストを生成しながら処理を行うために、メモリ効率の点ではなはだ無駄が多い。 そこで、一旦確保済みのデータの配列領域の内部（in-place:インプレース）で処理を進めるように工夫すると良い。

インプレースなリストの分割の具体的な手順

前節で述べたとおり、リストの分割を行なう際、データの臨時置き場が必要となるようではメモリー効率が悪いので、リストの前半部分にはピボット以下の要素が、後半にはピボットより大きな要素は配されるよう、「リスト上で」並べ替えを行なう。そのとき、前半部と後半部それぞれの中では、データの大小関係はでたらめで構わない。

そこで、下図のように、リストの先頭から後方に向かって「動く」変数 $i$ と、後方から前方に向かう変数 $j$ を用意する。 $i$ が指す場所の値がピボットより大きく、$j$ が指す場所がピボット以下なら、$i$と$j$の場所の値を交換しながら、$i$と$j$の大小関係が逆転するまでこれを続けたとしよう。すると、最終的に、$j$以下の場所にはピボット以下の要素、$i$以上の場所にはピボットより大きな要素が並んでいるはずである。

クィックソートのコーディングの例

以上のアイデアを元に、リストx[]のfirst番目からlast番目までの区間をソートする関数をPythonでコーディングした例を示す：

def quick_sort(first, last, x):
    if first==last:
        return
    ip=first
    while ip<=last:
        pv=x[ip]
        i=first
        j=last
        while True:
            while i<=last and x[i]<=pv:
                i=i+1
            while j>=first and x[j]>pv:
                j=j-1
            if i<j:
                x[j],x[i] = x[i],x[j]
            else:
                break
        if j<last:
            quick_sort(first,j,x)
            quick_sort(i,last,x)            
            return
        ip=ip+1
    return

　練習：クイックソート

上記の関数の設計を参考に、クイックソートで昇順にリストを整列するプログラムを完成させ、動作を確認しなさい。

さらに、上記のコードを手直しして、クィックソートで降順に整列するプログラムを作成しなさい。

　練習：大きなデータの統計量

ある調査で得た100万件のデータを、ファイルsample-big-array.txtとして用意した。 このデータは、正の整数値が各行１つずつ、100万行分記されたテキストファイルである。 このデータを読みこんで、中央値、最頻値、平均、分散を求めるコードを作成してみなさい。

　ヒント

2．ボトムアップなアプローチ：マージソート

すでに整列済みの２つのリスト $[a_i]$ $(i=1,\cdots ,n)$ と $[b_j]$ $(j=1,\cdots ,m)$ が用意されていたとする。 それらを元にすれば、２つのリストを併合（merge）して、整列されたリスト $[c_k]$ $(k=1,\cdots ,n+m)$ を容易に生成することができる。

具体的には、リスト $a$ と $b$ の先頭から、順にデータを読み、大小を比較して、小さいほうを $c$の末尾に追加していく作業を繰り返せばよい。 リストの最後まで 読み込んだら、そのリストの読み込みはそこで止め、まだ読み込みが終わっていないほうのリストの残りの部分をさらに$c$に加える。 こうして、全てのデータを$c$に「転写」したら、作業は完了である。 併合の際、$a$と$b$の（読み出しを終えていない箇所の）先頭のみを比較し・取り出せば良いので、その手間（処理回数）は、リストの要素数程度である。

並べ替えたいデータが、予め、小さな破片に分割されていたとする。すると、上記の手続きを、全体が１つのリストに併合されるまで繰り返して適用すると、最終的に得られるリストの内容は、きちんと整列されているはずである。 その様子を図に示す：

このように、分割と併合を組み合わせてデータを整列するアルゴリズムは併合ソート（マージソート: merge sort）と呼ばれ、高速で性質が良いことが知られており、実用上も重要である。 クイックソートがトップダウン的なアプローチとすれば、マージソートは、ボトムアップ的な手法と言うことができるだろう。 ここでは、マージソートによってリストを並べ替える関数 merge_sort() を設計してみよう：

これをPythonの関数としてコーディングした例を示す：

def merge_sort(first, last, x, w):
    if first==last:
        return
    m = (first + last)//2
    merge_sort(first,m,x,w)
    merge_sort(m+1,last,x,w)
    perform_merge(first, m, m+1, last, x, w)

ここで、リスト w[ ]は、併合の際のデータの「仮置き場」である。 関数の中で、分割した２つの区間の併合を行なうために、さらに別の関数perform_merge()を呼び出している。 そちらをコーディングした例を以下に示す：

def perform_merge(i1, i2, j1, j2, x, w):
    k = i1
    i=i1
    j=j1
    while True:
        if i<=i2 and (j>j2 or x[i] <= x[j]):
            w[k] = x[i]
            i=i+1
        elif j<=j2 and (i>i2 or x[i] > x[j]):
            w[k] = x[j]
            j=j+1
        else:
            break
        k=k+1

    for k in range(i1,j2+1,1):
        x[k] = w[k]

　練習：マージソート

上記の関数の設計を参考に、マージソートで昇順にリストを整列するPythonプログラムを完成させ、動作を確認しなさい。

さらに、上記のコードを手直しして、マージソートで降順に整列するプログラムを作成しなさい。

3．分割統治アルゴリズム

このページに登場したふたつのアルゴリズム（クイックソートとマージソート）は、いずれも、問題をより規模の小さな問題に分割し、 それぞれの結果を統合して大きな問題を解く、というアプローチで組み立てられている。 このようなアルゴリズムは分割統治アルゴリズム(divide and conquer algorithms) と呼ばれ、ソーティングに限らず、いくつもの実用的で重要な応用例が知られている。

大きな問題が与えられた際、それを小さな問題に分解してみてはどうか、とは誰でも思いつくだろうが、分割統治が上手く働くためには、問題を分割するだけでは不十分で、分割によって生じた部分同士がお互いに依存し合わないようになっていなければならない。 例えば、クィックソートの過程で、生成した部分列内の整列はその部分列の中だけで関係しており、別の部分列の状態は全く処理に関係しない。 マージソートでも、併合は二つの部分列の間だけで行なわれる。 加えて、問題の大小に関わらず、必要な手続きが全く同様（あるいは、「相似」）であれば、以下のように、再帰によって簡潔にそのアルゴリズムを記述できる：

データ $x$ が、いくつかの部分 $[x_i]$ に分解することができ、それぞれの「小問題」についての結果（解）が $f(x_i)$ で与えられるとしよう。 さらに、$x$ に対する結果が、部分のそれから「合成」できる、すなわち、$f(x)=g([f(x_i)])$ となるような手続き $g$ が与えられるとき、 「関数」$f$ は、形式的に、

によって再帰的に定義できる。

　練習：分割統治アルゴリズムとしてのソーティング

このページで示したクィックソートとマージソートの関数の例を読み、上記の分割統治の形式的な関数定義との対応関係（Pythonのコードのどの箇所が、形式的な定義の何行目と対応しているか、および、$[x_i]$は何に相当しているか）を示せ。