芋の独り言

当ブログへのアクセスは当ブログのプライバシーポリシーに同意したものとみなします.

クイックソート

の228~233ページに書いてある”クイックソート”をPythonで再現してみました. こんなことしなくても,ソートするメソッドは用意されているとは思いますが, C言語で書かれたものをPythonで再現してみようと思いまして. CとPythonは思想が違うので互換性はないと思いますが,どちらかで再現できないということはないと思ったので,なんとなくやってみました.


# クイックソート

# 入れ替えるメソッド
def swap(a: list,x: int,y: int):
    
    t    = a[x]
    a[x] = a[y]
    a[y] = t
    
    return a

# ソートするメソッド
def quick(a: list,left: int,right: int) -> list:
    
    pl = left  # 左カーソル
    pr = right # 右カーソル
    pivot = a[int((pl+pr)/2)] # 枢軸(中央の要素)

    # 配列の分割
    while True:
        # a[pl] >= pivot となる要素が見つかるまで右に走査
        while a[pl] < pivot:
            pl += 1
        # a[pr] <= pivot となる要素が見つかるまで左に走査
        while a[pr] > pivot:
            pr -= 1
            
        if pl <= pr:
            a = swap(a,pl,pr)
            pl += 1
            pr -= 1

            
        if pl > pr:
            break

    # 再帰
    if left < pr:
        a = quick(a,left,pr)
    if pl < right:
        a = quick(a,pl,right)

    return a


if __name__ == "__main__":
    print("quick sort test")

    import random
    import matplotlib.pyplot as plt
    import matplotlib.animation as animation

    #fig = plt.figure()
    fig, ax = plt.subplots(figsize=(4, 4))
    ax.grid()
    plotdata =[]

    
    test = [random.randrange(1,100,1) for i in range(100)]
    #print(test)
    plotdata.append(ax.bar([i for i in range(100)],height=test,color="steelblue",edgecolor='none'))
    
    def plot_quick(a: list,left: int,right: int) -> list:
        pl = left; pr = right; pivot = a[int((pl+pr)/2)] 

        while True:
            while a[pl] < pivot:
                pl += 1
            while a[pr] > pivot:
                pr -= 1
            
            if pl <= pr:
                a = swap(a,pl,pr)
                pl += 1
                pr -= 1
            if pl > pr:
                break

        plotdata.append(ax.bar([i for i in range(100)],height=a,color="steelblue",edgecolor='none'))
        
        if left < pr:
            a = plot_quick(a,left,pr)
        if pl < right:
            a = plot_quick(a,pl,right)

        return a

    test = plot_quick(test,0,len(test)-1)
    #print(test)
    plotdata.append(ax.bar([i for i in range(100)],height=test,color="steelblue",edgecolor='none'))
    
    anim = animation.ArtistAnimation(
        fig,
        plotdata, 
        interval = 200
        )
    anim.save("res_quick_sort.mp4", writer = 'ffmpeg')
    anim.save("res_quick_sort.gif", writer='imagemagick')

    print("finish")

以上においてmp4,gifアニメ化するには,以上のスクリプトと同じディレクトリ下にffmpegがあるか,ffmpegがインストールされている状態でなければなりません. imagmagickについても同じです. どちらもLinux(私はWSLのUbuntuで試してみましたが)環境ならば,

sudo apt-get install ffmpeg
sudo apt-get install imagemagick

でインストールできます.

スクリプトを実行したときにできるgif画像が以下です. 値はランダムに設定しているため,実行すると,毎回変わりますので以下と同じ画像にはなりません. gif画像ならはてなブログに簡単に貼れるので便利.ですが,mp4よりサイズが大きくなってしまいました...

f:id:kusoimox:20200107134322g:plain
ソートされていく様子を可視化


もう一つ注意すべきことがあります. WSLで以上のスクリプトを実行すると,

qt.qpa.screen: QXcbConnection: Could not connect to display :0.0
Could not connect to any X display.

というエラーが出ます. matplotlib・ffmpegimagemagickのいずれかが原因のような気がします. とりあえず,このエラーを解消するには kusoimox.hatenablog.jp でやったのと同じようにXlaunch をスクリプトを実行する前に起動しておくことです. (やり方はこちらのサイトを参考に) そうすると,スクリプトが実行されます. その際に

QStandardPaths: XDG_RUNTIME_DIR not set, defaulting to '/tmp/runtime-ユーザ名'

と出ますが,スクリプトは最後まで実行されますので気にしなくてもよいでしょう.

参考リンク