「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#22

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

6-6 クイックソート

最も高速なソートの一つとして知られており、広く利用されています。
クイックソートはグループわけの基準である枢軸を境に以上以下のグループで分ける手法を取ります。
枢軸は任意です。

最初に配列を2つのグループに分割する手順を考えます。
任意の数字を枢軸とした際、双方向バブルソートと同じように左右それぞれから走査し、枢軸と比較して以上、以下のグループ分けをします。添字について、左端側をpl、右端側をprとします。

この時配列aについて
・枢軸以下のグループ:a[0], ・・・, a[pl - 1]
・枢軸以上のグループ:a[pr + 1],・・・, a[n - 1]
というグループ分けができます。
また、pl > pr +　1 のときに限り
・枢軸と一致するグループ：a[pr + 1], ・・・, a[pl - 1]
というグループができます。

list6-10

#配列の分割

from typing import MutableSequence

def partition(a: MutableSequence) -> None:
    """配列を分割して表示"""
    n = len(a)
    pl = 0 #左カーソル
    pr = n - 1 #右カーソル 
    x = a[n // 2] # 枢軸(中央の要素)
    
    while pl <= pr: #配列aを枢軸xで分割
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    print(f'枢軸の値は{x}です。')
    
    print('枢軸以下のグループ')
    print(*a[0 : pl])
    
    if pl > pr + 1:
        print('枢軸と一致するグループ')
        print(*a[pr + 1 : pl])
        
    print('枢軸以上のグループ')
    print(*a[pr + 1 : n])
    
if __name__ == '__main__':
    print('配列を分割します。')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
        
    partition(x) #配列xを分割して表示

クイックソート

配列の分割を発展させることで、クイックソートのアルゴリズムとなります。
left(先頭の要素）、right(末尾の要素)としたとき
・prが先頭より右側に位置する(left < pr)のであれば、左グループを分割。
・plが末尾より左側に位置する(right > pl)のであれば、右グループを分割します。

list6-11

# クイックソート

from typing import MutableSequence

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]をクイックソート"""
    pl = left #左カーソル
    pr = right #右カーソル
    x = a[(left + right) // 2] #枢軸(中央の要素)
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    if left < pr: qsort(a, left, pr)
    if pl > right: qsort(a, pl, right)
        
def quick_sort(a: MutableSequence) -> None:
    """クイックソート"""
    qsort(a, 0, len(a) - 1)
    
if __name__ == '__main__':
    print('クイックソート')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
    
    quick_sort(x) #配列xをクイックソート
    
    print('昇順にソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

一種の分割統治法であるため、再帰呼び出しを用いて簡潔に実現ができます。
また、クイックソートは安定ではありません。

コラム6-3 クイックソートにおける分割の過程の表示

list6C-3

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]をクイックソート(配列の分割過程を表示)"""
    pl = left #左カーソル
    pr = right #右カーソル
    x = a[(left + right) // 2] #枢軸(中央の要素)
    
    print(f'a[{left}]～a[{right}]:', *a[left : right + 1])
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    if left < pr: qsort(a, left, pr)
    if pl > right: qsort(a, pl, right)

# クイックソート

from typing import MutableSequence

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]をクイックソート"""
    pl = left #左カーソル
    pr = right #右カーソル
    x = a[(left + right) // 2] #枢軸(中央の要素)
    
    print(f'a[{left}]～a[{right}]:', *a[left : right + 1])
    
    while pl <= pr:
        while a[pl] < x: pl += 1
        while a[pr] > x: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1
            
    if left < pr: qsort(a, left, pr)
    if pl > right: qsort(a, pl, right)
        
def quick_sort(a: MutableSequence) -> None:
    """クイックソート"""
    qsort(a, 0, len(a) - 1)
    
if __name__ == '__main__':
    print('クイックソート')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
    
    quick_sort(x) #配列xをクイックソート
    
    print('昇順にソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

非再帰的クイックソート

スタックを活用することで、非再帰的なプリグラムを作ることができます。

list6-12

#クイックソート(非再帰版)

from stack import Stack #list4c-1
from typing import MutableSequence

def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]をクイックソート(非再帰版)"""
    range = Stack(right - left + 1)
    
    range.push((left, right))
    
    while not range.is_empty():
        pl, pr = left, right = range.pop() #左右のカーソルを取り出す
        x = a[(left + right) // 2] #枢軸()中央の要素
        
        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1
            
        if left < pr: range.push((left, pr)) #左グループのカーソルを保存
        if pl < right: range.push((pl, right)) #右グループのカーソルを保存

枢軸の選択

枢軸の選択方法はクイックソートの実行効率に大きく影響を与えます。
偏った分割の繰り返しは高速なソートを期待できないため、値としての中央値を枢軸とするのが理想です。

時間計算量

クイックソートは要素数が小さい場合はそれほど高速ではありません。

そこで要素が小さい場合は単純挿入ソートに切り替え、枢軸については以下の考え方を用います。
・分割すべき配列の先端要素/中央要素/末尾要素の3要素をソートして、さらに中央要素と末尾から2番目の要素を交換する。枢軸として末尾から2番目に要素の値a[right - 1]を採用するとともに、分割の対象をa[left + 1] ～a[right -2]に絞り込む。

list6-13

#クイックソート(第2版)

from typing import MutableSequence

def sort3(a: MutableSequence, idx1: int, idx2: int, idx3: int):
    """a[idx1], a[idx2], a[idx3]を昇順にソートして中央値の添字を返却"""
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    if a[idx3] < a[idx2]: a[idx3], a[idx2] = a[idx2], a[idx3]
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    return idx2

def insertion_sort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]を単純挿入ソート"""
    for i in range(left + 1, right + 1):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j - 1]
            j -= 1
        a[j] = tmp
        
def qsort(a: MutableSequence, left: int, right: int) -> None:
    """a[left]～a[right]をクイックソート""" 
    if right - left < 9: #要素数が9未満であれば単純挿入ソートに切り替える
        insertion_sort(a, left, right)
    else:
        pl = left #左カーソル
        pr = right #右カーソル
        m = sort3(a, pl, (pl + pr) // 2, pr)
        x = a[m]
        
        a[m], a[pr - 1] = a[pr - 1], a[m]
        pl += 1
        pr -= 2
        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1
                
        if left < pr: qsort(a, left, pr)
        if pl < right: qsort(a, pl, right)
            
def quick_sort(a: MutableSequence) -> None:
    """クイックソート"""
    qsort(a, 0, len(a) - 1)
    
if __name__ == '__main__':
    print('クイックソート(第2版)')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
    
    quick_sort(x) #配列xをクイックソート
    
    print('昇順ソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

コラム6-4 sorted関数によるソート
pythonはソートを行うためのsorted関数を組み込み関数として提供します。この関数は、受け取った(任意の方の)イテラブルオブジェクトの要素をソートして、list型のリストとして返却します。そのため、ソートを行う関数というよりも「ソートを行った後の並びを新しいリストとして生成して返却する関数」です。

list6C-4

#sorted関数によるソート

print('sorted関数によるソート')
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成

for i in range(num):
    x[i] = int(input(f'x[{i}]：'))
    
#配列xを昇順にソート
x = sorted(x)
print('昇順にソートしました。')
for i in range(num):
    print(f'x[{i}]={x[i]}')
    
#配列xを降順にソート
x = sorted(x, reverse=True)
print('降順にソートしました。')
for i in range(num):
    print(f'x[{i}]={x[i]}')

6-7マージソート

配列を前半部と後半部の二つに分けてそれぞれをソートした下のをマージする作業を繰り返すことによってソートを行うアルゴリズムです。

最初に、ソート済みの配列をマージすることでマージの理解を深めましょう。

list6-14

#ソート済み配列のマージ
from typing import Sequence, MutableSequence

def merge_sorted_list(a: Sequence, b:Sequence, c:MutableSequence) -> None:
    """ソート済み配列aとbをマージしてcに格納"""
    pa, pb, pc = 0, 0, 0 #カーソル
    na, nb, nc = len(a), len(b), len(c) #要素数
    
    while pa < na and pb < nb: #小さい方を格納
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1
        
    while pa < na: #aに残った要素をコピー
        c[pc] = a[pa]
        pa += 1
        pc += 1
        
    while pb < nb: #bに残った要素をコピー
        c[pc] = b[pb]
        pb += 1
        pc += 1
        
if __name__ == '__main__':
    a = [2, 4, 6, 8, 11, 13]
    b = [1, 2, 3, 4, 9, 16, 21]
    c = [None] * (len(a) + len(b))
    print('二つのソートずみ配列のマージ')
        
    merge_sorted_list(a, b, c) #配列aとbをマージしてcに格納
    
    print('配列aとbをマージして配列cに格納しました。')
    print(f'配列a：{a}')
    print(f'配列b：{b}')
    print(f'配列c：{c}')

マージソート

ソート済み配列のマージを応用して、分割統治法によってソートを行うアルゴリズムがマージソートです。

list6-15

#マージソート
from typing import MutableSequence

def merge_sort(a: MutableSequence) -> None:
    
    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left]～a[right]を再帰的にマージソート"""
        if left < right:
            center = (left + right) // 2
            
            _merge_sort(a, left, center) #前半部をマージソート
            _merge_sort(a, center + 1, right) #後半部をマージソート
            
            p = j = 0
            i = k = left
            
            while i <= center:
                buff[p] = a[i]
                p += 1
                i += 1
                
            while i <= right and j < p:
                if buff[j] <= a[i]:
                    a[k] = buff[j]
                    j += 1
                else:
                    a[k] = a[i]
                    i += 1
                k += 1
                
            while j < p:
                a[k] = buff[j]
                k += 1
                j += 1
                
    n = len(a)
    buff = [None] * n
    _merge_sort(a, 0, n - 1)
    del buff
        
if __name__ == '__main__':
    print('マージソート')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
        
    merge_sort(x) #配列xをマージソート
    
    print('昇順にソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

今回は以上です。
ありがとうございました。