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

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

第6章 ソート

いよいよソートに入ります。ソートができるようになると、プログラムの幅も広がりそうですね。

ソートアルゴリズムの安定性

ソートにも安定なものとそうでないものがあります。
安定なソートは同一キーをもつ要素がソート前後で維持されます。安定でない場合たまたま同一キーが維持されることもありますが、保証されているわけではありません。

内部ソートと外部ソート

最大で30枚のカードを並べることができる机の上で、トランプのカードをソートすることを考えます。もしカードが500枚の場合机の上には置ききれないため、別の机を用意するなどが必要で、プログラムでも同様です。そこで、
内部ソート…ソートの対象となるデータが、一つの配列上に格納できる場合に用いるアルゴリズムで、カードは配列上に展開された要素に相当します。
外部ソート…ソートの対象となるすべてのデータが大量であり、一度に並べ替えることができない場合に用いるアルゴリズムで、内部ソート応用です。実現には作業用ファイルなどが必要でアルゴリズムも複雑なため、本書では内部ソートのみを扱います。

ソートの考え方

ソートアルゴリズムの3大要素は交換・選択・挿入です。ほとんどのソートアルゴリズムはこれらの要素を応用したものです。

6-2 単純交換ソート(バブルソート)

隣り合う二宇の要素の大小関係を調べて、必要に応じて交換をっ繰り返すのが、単純交換ソートです。

[6, 4, 3, 7, 1, 9, 8]というならびがあるとすると、昇順に並び替える場合、末尾から注目して交換を進めます。

比較→交換後
9>8→8<9
1<8→1<8
7>1→1<7
・・・
と繰り返し、これを何巡かすることで、ソートします。

要素数nの配列に対して、n - 1回の比較・交換を行うと、最小要素が先頭に移動します。この一連の比較・交換の作業をパスといいます。

パスを行うたびにソートの対象要素が1個ずつ減っていくため、1パス目の比較回数はn - 1回であったのに対して、2パス目はn - 2回となります。
パスをk回行うと、先頭側k個の要素がソート済みとなる事がわかりました。全体のソートを完了させる為に必要なパスはn - 1回です。

単純交換ソートプログラム

単純交換ソートプログラムのアルゴリズムをプログラムとして実現します。
変数iの値を0からn - 2までインクリメントして、パスをn - 1回行うことにするとプログラムはlist6-1のようになります。

list6-1

#単純交換ソート
from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
    """単純交換ソート"""
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1, i, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                
if __name__ == '__main__':
    print('単純交換ソート(バブルソート)')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
        
    bubble_sort(x) #配列xを単純交換ソート
    
    print('昇順にソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

比較のために着目する2要素は、a[j - 1]とa[j]です。
走査は配列の末尾から先頭に向かって行うため、走査におけるjの開始値は、すべてのパスで末尾の添字であるn - 1です。
走査の過程では、2要素a[j - 1]とa[j]を比較して、前者の方が大きければ交換します。これを先頭側に向かって行うため、jの値は一つずつデクリメントしていきます。各パスにおいて先頭i個の要素はソート済みであって、未ソート部はa[i]～a[n - 1]のため、jのデクリメントはそのあたいがi + 1になるまで行います。

単純交換ソートは隣り合う要素のみを交換するため安定です。
要素を比較する合計はn(n - 1)/2となります。
ただし実際に要素を交換する回数は配列の要素の値によって左右されるため、平均値は比較回数の半分のn(n - 1)/4回です。

交換過程の表示

list6-2

#単純交換ソート
from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
    """単純交換ソート<<交換過程を表示>>"""
    ccnt = 0 #比較回数
    scnt = 0 #交換回数
    n = len(a)
    for i in range(n - 1):
        print(f'パス{i + 1}')
        for j in range(n - 1, i, -1):
            for m in range(0, n-1):
                print(f'{a[m]:2}' +  ('  'if m != j - 1 else '  +' if a[j - 1] > a[j] else ' -' ), end='')
            print(f'{a[n - 1]:2}')
            ccnt += 1
            if a[j - 1] > a[j]:
                scnt += 1
                a[j - 1], a[j] = a[j], a[j - 1]
        for m in range(0, n - 1):
            print(f'{a[m]:2}', end='  ')
        print(f'{a[n - 1]:2}')
    print(f'比較は{ccnt}回でした。')
    print(f'交換は{scnt}回でした。')
                
if __name__ == '__main__':
    print('単純交換ソート(バブルソート)')
    num = int(input('要素数：'))
    x = [None] * num #要素数numの配列を生成
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]：'))
        
    bubble_sort(x) #配列xを単純交換ソート
    
    print('昇順にソートしました。')
    for i in range(num):
        print(f'x[{i}]={x[i]}')

交換を行う場合は+しない場合は-を表示します。

アルゴリズムの改良(1)

ソートが完了した際、それ以降のパスで交換が行われることはありません。
ある回数における要素の交換回数が0であれば、すべての要素がソート済みであるため。それ以降は不要であって、ソート作業は打ち切れます。
打ち切りを導入することで、短時間でソートが完了します。

list6-3

def bubble_sort(a: MutableSequence) -> None:
    """単純交換ソート(第2版：交換回数による打ち切り)"""
    n = len(a)
    for i in range(n - 1):
        exchng = 0 #パスにおける交換回数
        for j in range(n - 1, i , -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
        if exchng == 0:
            break

アルゴリズムの改良(2)

一連の比較・交換を行うパスにおいて、ある時点以降に交換が行わなければ、それより先頭側はソート済みです。

list6-4

def bubble_sort(a: MutableSequence) -> None:
    """単純交換ソート(第3版)：走査範囲を限定"""
    n = len(a)
    k = 0
    while k < n - 1:
        last = n - 1
        for j in range(n - 1, k, 1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
        k = last

lastは、各パスで最後に交換した2要素の右側要素の添字を格納するための変数です。交換を行うたびに右側要素の添字の値をlastに代入します。
パスが終了した時点で、lastの値をkに代入することによって、次に行われるパスの走査範囲をa[k]までに限定します。(次のパスで最後に比較される2要素はa[k]とa[k + 1]となる)

シェーカーソート(双方向バブルソート)

先頭のみソートされていない状況の場合、ソート作業を早期に打ち切ることができません。
そこで、奇数パスでは最小要素を先頭に移動させ、偶数パスでは最大要素を末尾側に移動するというように走査方向を交互に変えると、ここで考えているような並びを、少ない回数でソートできます。

list6-5

def shaker_sort(a: MutableSequence) -> None:
    """シェーカーソート(双方向バブルソート)"""
    left = 0
    right = len(a) - 1
    last = right
    while left < right:
        for j in range(right, left, -1):
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                last = j
        left = last
        
        for j in range(left, right):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                last = j
        right = last

コラム6-1 算術演算に利用する組み込み関数

Table6C-1 算術演習に利用する組み込み関数
abs(x)	数値xの絶対値を返す
bool(x)	xの理論値(TrueかFalse)を返す
comp(real, img)	値real + img * 1jの複素数を返却するか、文字列や数値を複素数に変換した値を返却する。imgが省略された場合はゼロとみなす。realとimgの両方が省略された場合は0jを返却する。
divmod(a, b)	数値aをbで除したときの商と剰余で構成されるタプルを返却する。
float(x)	文字列あるいは数値を浮動小数点に変換した値を返却する。引数が省略された場合は0.0を返却する。
hex(x)	整数値xの、0xで始まる16真表記による文字列を返却する。
int(x, base)	xをint型整数に変換した値を返却する。baseは0～36の範囲でなければならず、省略された場合は10とみなす。
max(args)	引数の最大値を返却する。
min(args)	引数の最小値を返却する。
oct(x)	整数値xの、0oで始まる8進表記による文字列を返却する。
pow(x, y, z)	xのy乗を返却する。zが指定された場合は、pow(x, y) % z と同じ計算になる。
round(n, ndigits)	nの小数部をndigits桁に丸めた値を返却する。ndigitsがNoneであるか省略された場合は入力値に、最も近い整数を返却する。
sum(x, start)	startとxの要素を先頭から末尾へと順に合計して総和を返却する。startのデフォルトは0である

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