LoginSignup
0

More than 1 year has passed since last update.

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

Last updated at Posted at 2022-02-28

【出典】「新・明解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]}')

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0