Pythonで学ぶアルゴリズム、ソート第5段は「クイックソート」です。クイックソートは再帰的プログラミングを使って配列の種類によっては比較的高速にソートできるアルゴリズムです。ここではPythonで動画を作る方法を紹介しながら理解する事を目標とします。
こんにちは。wat(@watlablog)です。ここでは有名なソートであるクイックソートのアルゴリズムを学びます！
クイックソートの概要
特徴や計算量
クイックソート（Quick sort）とは、任意の適当な基準値（ピボット）を決め、基準値よりも小さいグループと大きいグループに分けて並べ替えを行う特徴を持つアルゴリズムです。
グループ分けは配列がそれ以上分割できなくなるまで繰り返し行うため、一般に再帰処理を使ったプログラミングがされます。
配列を分割しながらソートしていく分割統治法の一種でもあります。
再帰処理についてはマージソートで説明しましたので、まだ曖昧という方は是非「Pythonでマージソートの挙動を可視化してスッキリするページ」の記事をご覧ください。
クイックソートはその他のソートと比べて高速と言われており、平均計算量は\(O(N \log N)\)です。しかし、データの初期並びやピボットの選び方によってばらつきはあり、最悪計算量は\(O(N^{2})\)です。
また、同一値の順番がソート後に入れ替わる可能性もあり、マージソートと違って安定ソートではありません。
クイックソートの手順
コードを書く前に、クイックソートの手順を確認します。
クイックソートは、まず始めに配列の中からピボットと呼ばれる基準値を選びます。その後、基準値より小さい値を左側に、基準値より大きい値を右側に順番に移動させます。
この操作を図解したものを下に示します。
この操作を大小グループ毎にこれ以上分割できない最後まで繰り返す（再帰処理）と、ピボットの位置が全て確定され、全ての数のソートが完了します。
以下の動画は10個のデータに対するクイックソートの動画です。半分ずつ処理が進んでいく様子がわかります…かね？わかりにくいかも。
データが少ないと動画ではよくわかりませんが、後半に100個のデータを使った動画とその作り方を載せています。
Pythonでクイックソートをするコード
クイックソートの関数
ここからPythonでクイックソートをコーディングしていきます。
以下の全コードには、def quick_sort()にソートしたい配列（リスト）を渡して、ソート結果を受け取る形式で書いています。
pivotはリストの中心を使う仕様にしていますが、クイックソートはピボットの選び方で性能に差が出ます。改良のためにランダムに選ぶか、ランダムに数個選んだ中央値を使うか…といった選び方があるとの事。
いずれもpivot部分の変更で実装可能です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import random # クイックソートを行う関数 def quick_sort(x): # 基準値を抽出(半分の位置の値) n = len(x) pivot = x[int(n / 2)] # i番目の値と基準値を比較して左l、右r、真ん中mに追加 l = [] r = [] m = [] for i in range(n): sample = x[i] if sample < pivot: l.append(sample) elif sample > pivot: r.append(sample) else: m.append(sample) # lとrの場合でそれぞれ再帰処理による分割を行う if l: l = quick_sort(l) if r: r = quick_sort(r) return l + m + r # データをランダムに用意してソートを実行 x = random.sample(range(10), k=10) list = quick_sort(x) print('initial array:', x) print('quick sorted:', list) |
以下が結果。ソートされました。
|
1 2 |
initial array: [5, 8, 4, 2, 3, 0, 9, 7, 1, 6] quick sorted: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] |
クイックソートの動画を作成するコード
ソートアルゴリズムは動画にするとなぜか癒されるので、今回も恒例行事として動画作成コードを紹介します。
マージソートの時は再帰処理をそのまま使って動画を作成していましたが、かなり無理やり感がありました。今回は再帰を非再帰に書き換える事で、自然と画像保存ができるようにしました。
再帰を非再帰にする方法は以下のQiita記事を参考にさせて頂きました。ありがとうございます。
「Qiita：Python 再帰関数から非再帰関数への変換を考える」
全コードはこちら。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
import random import numpy as np import glob import os from PIL import Image from matplotlib import pyplot as plt # GIFアニメーションを作成 def create_gif(in_dir, out_filename): path_list = sorted(glob.glob(os.path.join(*[in_dir, '*']))) # ファイルパスをソートしてリストする imgs = [] # 画像をappendするための空配列を定義 # ファイルのフルパスからファイル名と拡張子を抽出 for i in range(len(path_list)): print(len(path_list)) img = Image.open(path_list[i]) # 画像ファイルを1つずつ開く # 最後の画像だけ10枚追加して余韻を残す。 if i == len(path_list) - 1: for j in range(10): imgs.append(img) imgs.append(img) # 画像をappendで配列に格納していく # appendした画像配列をGIFにする。durationで持続時間、loopでループ数を指定可能。 imgs[0].save(out_filename, save_all=True, append_images=imgs[1:], optimize=False, duration=50, loop=0) return # プロットする関数 def plot(data, save_dir): # ここからグラフ描画 i = len(glob.glob1(save_dir, "*.png")) print(i) # フォントの種類とサイズを設定する。 plt.rcParams['font.size'] = 14 plt.rcParams['font.family'] = 'Times New Roman' # 目盛を内側にする。 plt.rcParams['xtick.direction'] = 'in' plt.rcParams['ytick.direction'] = 'in' # グラフの上下左右に目盛線を付ける。 fig = plt.figure() ax1 = fig.add_subplot(111) ax1.yaxis.set_ticks_position('both') ax1.xaxis.set_ticks_position('both') # 軸のラベルを設定する。 ax1.set_xlabel('x') ax1.set_ylabel('y') ax1.set_xticks(np.arange(0, len(x) + 1, len(x)/10)) ax1.set_xlim(0, len(x) + 1) ax1.set_ylim(0, len(x) + 1) # データプロットの準備。 ax1.bar(np.arange(1, len(data) + 1, 1), data, label='data') plt.text(1, int(len(x) * 0.9), 'count=' + str(i), fontsize=20) # グラフを表示する。 fig.tight_layout() fig.legend() # dirフォルダが無い時に新規作成 if os.path.exists(save_dir): pass else: os.mkdir(save_dir) # 画像保存パスを準備 path = os.path.join(*[save_dir, str("{:05}".format(i)) + '.png']) # 画像を保存する plt.savefig(path) plt.close() return # クイックソートを行う関数 def quick_sort(lt): length = len(lt) stack = [(0, length - 1)] while len(stack) > 0: l, r = stack.pop() if l >= r: continue i = l j = r p = lt[l + int((r - l) / 2)] while i < j: plot(lt, 'img_quick-sort') print('list=', lt) while lt[i] < p: i += 1 while lt[j] > p: j -= 1 if i < j: if lt[i] == lt[j]: j -= 1 else: lt[i], lt[j] = lt[j], lt[i] stack.append((j + 1, r)) stack.append((l, i - 1)) return # データをランダムに用意してソートを実行 x = random.sample(range(100), k=100) print('initial array:', x) quick_sort(x) print('quick sorted:', x) create_gif('img_quick-sort', 'movie-quick-sort100.gif') |
コードを実行すると、movie-quick-sort100.gifという動画が作成されます。是非色々なデータで遊んでみてください。
まとめ
この記事ではこれまで学んだ再帰プログラミングを使いながら、クイックソートをPythonで書いてみました。
また、ソート処理を可視化するために非再帰に変換、動画を作成するコードも作ってみました。
ソートアルゴリズムはプログラミング言語に標準で備わっている場合がほとんどですが、あえてアルゴリズムを学ぶのは基本情報等の資格取得目的以外にもプログラミングの学習として良いのではないでしょうか。
クイックソートを書けるようになりました！
Twitterでも関連情報をつぶやいているので、wat(@watlablog)のフォローお待ちしています！