pythonでクイックソートを実装してみた
今回はソートアルゴリズムの中でも最速であるクイックソートをpythonで実装していきたいと思います．
実装部分に興味がある人は目次からクイックソートの実装を押して読み飛ばしてください.
目次
クイックソートとは
一般的に最も高速なソートアルゴリズムとして知られています．ただしデータの並びによってはO(n2)になってしまうアルゴリズムになっています．
クイックソートの動作としては
- 配列全体に対して以下の動作を繰り返す
基本的にピボットの選び方は中央値がいいのですが，その値を当てることはできないので一般的にはデータ列からランダムに持ってきたり，数個のデータの中央値をとったりするそうです．
また，対象となるデータ列が少なくなってきたら別のアルゴリズムを適用するなどしてクイックソートは利用されているそうです．(参照)
上記の動作の説明だけではわかりづらいと思うので下図を追いながら動作を確認してみてください．
パーティションの実装
クイックソートの中の動作に出てきたパーティションをまずは実装していきたいと思います．
パーティションの動きとしては
- ピボットを定める
- 配列番号iまでにピボットよりも小さな要素をまとめ，配列番号i+1以上にピボットより大きな要素をまとめる
これらをまずは実装していきたいと思います．
import random def partition(A, start, end): pivot = A[end] i = start - 1 for j in range(start, end): if A[j] <= pivot: #A[i+1]の要素はピボットより大きい要素なので #A[i+1]とピボット以下の大きさの要素A[j]の位置を入れ替える i += 1 A[i], A[j] = A[j], A[i] A.insert(i+1, pivot) A.pop() return A = list(range(1,11)) random.shuffle(A) print(A) partition(A, 0, len(A)-1) print(A)
出力を確認すると
[1, 3, 8, 2, 4, 9, 5, 10, 7, 6] [1, 3, 2, 4, 5, 6, 9, 8, 10, 7]
一番後ろにいた要素6(配列をシャッフルしているので実行の度に変わります)が配列の中の正しい位置に移動していると思います．
これでクイックソートの中核となる処理を作ることができました.
クイックソートの実装
続いて実際にクイックソートを実装していきたいと思います．
実装には先ほど作成したパーティションも活用します．
パーティションに関して一部コードを書き換えています．
import random def partition(A, start, end): pivot = A[end] i = start - 1 for j in range(start, end): if A[j] <= pivot: i += 1 A[i], A[j] = A[j], A[i] A[i+1], A[end] = A[end], A[i+1] print(A) return i+1 def quicksort(A, start, end): if start < end: pivot_position = partition(A, start, end) quicksort(A, start, pivot_position -1) quicksort(A,pivot_position + 1, end) A = list(range(1,11)) random.shuffle(A) print(A) quicksort(A, 0, len(A)-1) print(A)
出力例
[4, 10, 9, 2, 8, 1, 3, 6, 7, 5] # 初期配列 [4, 2, 1, 3, 5, 9, 10, 6, 7, 8] # pivot = 5 [2, 1, 3, 4, 5, 9, 10, 6, 7, 8] # pivot = 3 [1, 2, 3, 4, 5, 9, 10, 6, 7, 8] # pivot = 1 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] # pivot = 8 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] # pivot = 7 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # pivot = 9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # ソート済み配列
徐々に配列がソートされていく様子がわかると思います．
コード解説
クイックソートの再帰関数部分を少しだけ補足しておきます．
" if start < end "
残りのコード部分に関しては
という処理を行なっているだけです．
パーティションの実装ができ，再帰関数の扱い方に慣れていれば意外と簡単に実装できますね．
もっとこんな実装があるよとかこれを実装してみて欲しいというようなものがあればコメントください！
pythonでマージソートを実装してみた
今回はソートアルゴリズムの中でも今まで学んできたものよりも高速なアルゴリズムであるマージソートに関してpythonで実装していきたいと思います．
マージソートは基本的なソートアルゴリズムと比べると少し実装しづらい部分はありますが，全体の流れを掴むことと再帰関数をしっかりと使いこなすことができればそれほど苦戦せずに実装できると思います．
目次
マージソートとは
マージソートは配列全体に対して次の処理を行うようなソートを指します．
指定されたn個の要素を含む部分配列をそれぞれn/2個の要素を含む2つの部分配列に分割する.
1.1 部分配列は一つの要素になるまで分割を続ける
2つの部分配列をそれぞれ順番通りに並ぶようマージ(合併)する
2.1 部分配列がなくなるまで繰り返す
これらの流れを下図で確認してください.
図で流れを抑えると処理の行い方がより明確に伝わったと思います．
マージソートの土台は配列全体の1/2の大きさの部分配列を作りだすことと部分配列を統合していくことで作ることができます．
また，この分割フェーズに関しては1/2にしていくことを繰り返す，つまり，log2n回の分割を行います．
一方でこの統合フェーズに関してはソート済みの配列を統合していきます．
つまり，必ずどちらかの配列の先頭要素のうち一つが統合後の配列の先頭要素になります．同様に統合後の二番目の配列要素に関してもどちらかの部分配列の要素にあり，この処理を繰り返していくことで統合することができます．よって，各階層でかかる計算量は常にO(n)となります．
これらのことよりマージソートはこれまで書いてきたソートアルゴリズムよりも早いO(nlogn)のアルゴリズムとなります．
マージソートの実装例
マージソートに関しての問題はALDS1_5_B:Merge Sortです．
マージソートの擬似コードなどが載っているので流れを確認したい方は見に行ってみてください.
では，早速実装していきたいと思います．
# mergesort import random #統合部 def merge(A, left, mid, right): L = A[left:mid] R = A[mid:right] for i in range(left,right): if len(L) == 0: A[i] = R.pop(0) elif len(R) == 0: A[i] = L.pop(0) elif L[0] <= R[0]: A[i] = L.pop(0) else: A[i] = R.pop(0) #分割部 def mergesort(A, left, right): if left + 1 < right: mid = (left + right)//2 mergesort(A, left, mid) mergesort(A, mid, right) merge(A, left, mid, right) print(A) A = [ i+1 for i in range(10)] random.shuffle(A) print(A) mergesort(A,0,len(A)) print(A)
出力例
[8, 9, 3, 7, 10, 4, 6, 5, 1, 2] [8, 9, 3, 7, 10, 4, 6, 5, 1, 2] [8, 9, 3, 7, 10, 4, 6, 5, 1, 2] [8, 9, 3, 7, 10, 4, 6, 5, 1, 2] [3, 7, 8, 9, 10, 4, 6, 5, 1, 2] [3, 7, 8, 9, 10, 4, 6, 5, 1, 2] [3, 7, 8, 9, 10, 4, 6, 5, 1, 2] [3, 7, 8, 9, 10, 4, 6, 1, 2, 5] [3, 7, 8, 9, 10, 1, 2, 4, 5, 6] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
コードの解説
mergesortの関数の部分では部分配列の位置を表すleftとright，また，その中央部分(分割部分)を表すmidをright - leftが2になるまで再帰的に呼び出しています．つまり，leftとrightに含まれる要素がそれぞれ一つになるまで呼び出しを続けています．
その後，再帰関数の呼び出しの逆順に統合部分の関数に値が投げられます．
統合部ではleftの位置にある配列Aの要素群とrightの位置にある配列Aの要素群の値の大小を群の先頭から順に比較しています．
一連の処理を終えると出力例の最終行のようにソートされた値が並ぶと思います．
再帰関数で作るフラクタル図形 ~コッホ曲線~
今回はフラクタル図形の各頂点の座標を求める問題に挑戦していきたいと思います．再帰関数の理解を深めるのにちょうどいい問題でしたのでぜひ挑戦してみてください．
目次
フラクタル図形とは
図形の部分と全体が自己相似（再帰）によってできているものをフラクタルと呼ぶそうです(wiki参照).
シェルピンスキーのギャスケット(初めて名前知りました…)がみなさん見たことあるフラクタル図形の一つだと思います．
フラクタル図形は自然界にもたくさんある形です．こういった幾何学模様は不思議な魅力があって綺麗に見えますよね.
コッホ曲線
コッホ曲線は先ほど説明したフラクタル図形の一つです.
線分を3等分し、分割した2点を頂点とする正三角形の作図するということを無限に繰り返すことによって得られる図形を指しています.
画像参考サイト
正三角形からこのコッホ曲線を描くと雪片のようになることでも有名です.
問題
今回扱う問題はALDS1_5_C: Koch Curveになります．
問題の内容としては入力nを受け,深さnの再帰呼び出しによって作成されるコッホ曲線の頂点の座標を出力するというものです.
作らなければならない動作としては
- 与えられた線分(p1, p2)を三等分にする
- 線分を三等分する2点(s, t)を頂点とする正三角形(s, t, u)を作成し，その座標を求める
- 新しくできた全ての線分[(p1, s),(s, u), (u, t), (t, p2)]に対して上記の処理を再帰的に繰り返す．
コード&解説
n=1の時は直感的にuの座標がわかると思うのですが，nが増えていくに連れてわかりづらくなると思います． (自分はここで詰まりました…)
ここで，点uの座標を求めるのに使うのが回転行列です．
原点中心に θ 回転して点 (x, y) が (x ', y ') に写るとすると、図形的考察または三角関数の加法定理より、x', y ' は以下のように表されることが分かる。
x'= x cosθ - y sinθ
y'= x sinθ + y cosθ
wiki参照
また，図形的考察をしてくれているサイトもあるのでこちらも参考にしてみてください(参考サイト).
では，これらの知識を活用して上記であげた動作をするプログラムを実装していきましょう.
import mathdef koch(n, p1, p2): if n == 0: return sx = 2p1[0]/3 + p2[0]/3 sy = 2p1[1]/3 + p2[1]/3 tx = p1[0]/3 + 2p2[0]/3 ty = p1[1]/3 + 2p2[1]/3 ux = (tx - sx)math.cos(math.radians(60)) - (ty - sy)math.sin(math.radians(60)) + sx uy = (tx - sx)math.sin(math.radians(60)) + (ty - sy)math.cos(math.radians(60)) + sy koch(n-1, p1, [sx, sy]) print(sx, sy) koch(n-1, [sx, sy], [ux, uy]) print(ux, uy) koch(n-1, [ux, uy], [tx, ty]) print(tx, ty) koch(n-1, [tx, ty], p2)
n = int(input()) #問題文より，端点がp1 = (0,0), p2 =(100,0)と指定されている p1 = [0, 0] p2 = [100, 0] print(p1[0], p1[1]) koch(n, p1, p2) print(p2[0], p2[1])
上記のコードを実行することでp1から順に繋がった形で線分の座標を出力することができます．
点uの座標を求める方法を考えるのに苦労しましたがコードにすると意外と簡潔になりますね．
再帰関数に関してはこの前
やったばかりなのでお手の物でした！
Pythonを使ってこれらの図形を実際に描くこともできるそうなので今度試してみたいと思います．
pythonで部分集合を探索する方法3選
前回の再帰に関する記事で組み合わせの列挙を扱いました．他の方法でも解いたみたいと考え，今回の記事を作成するに至りました．
目次
部分集合の問題って何？
部分集合を扱った問題がどのような問題なのかをまず解説していきます．
問題
n個の要素を持つ配列Aの要素を0個以上足し合わせることで作ることのできる整数を全て列挙してください．
このような問題があった時考えなければいけないのが足し合わせることのできる全ての配列要素の組み合わせを列挙し，それらの組み合わせを計算し，出力するということが考えられると思います．
このような組み合わせの列挙には配列の中の要素を選択するか，しないかという処理を全ての要素に行い，組み合わせを作ることでできます．
今回はこういった場合の組み合わせの列挙を3つの方法で作っていきたいと思います．
最後にはこういった組み合わせを使った問題を実際に解いてみたいと思います．
まずは選択する(1), しない(0)のリストをそれぞれの方法で作っていきます.
再帰関数を使った方法
まず，一つ目が自分で組み合わせを作り上げていくプログラムになります．再帰関数を用いて実際に自分で作るので実装力は身につくかもしれませんが，競技プログラミングなどではコードを書く速度を求められるのであまりお勧めはできません．
勉強がてら作ってみたいという人は挑戦してみてください.
def comb(i, A, ans): if i == n: ans.append(list(A)) return comb(i+1, A, ans) A[i] = 1 comb(i+1, A, ans) A[i] = 0 n = 5 A = [0]*n ans = [] comb(0, A, ans) print(ans)
出力
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1], ・ ・ ・ [1, 1, 1, 1, 0], [1, 1, 1, 1, 1]]
itertoolsを使った方法
二つ目が，itertoolsを用いた方法です．pythonの標準ライブラリの一つで効率的なループ処理を行ってくれます．
よく使うものとしては順列(n!)，組み合わせの数(nCr)がありますが，その他にもたくさんのことができるので気になる方はこちらから確認してみてください．
今回のような問題に使えるのがこのitertoolsの中の"product"になります．
上記で作成したような配列を一瞬で作ることができます．
出力に関しては似たような形なので省略します．
import itertools n = 5 print(list(itertools.product(range(2), repeat = n)))
bitを使った方法
三つ目が，二進数(bit)を用いた方法です．bitでこのような組み合わせを探索することをbit全探索というような呼び方をしたりします．
整数を2進数表記に変えてくれるpythonの組み込み関数binを用いることでbitの文字列を作ることができます．
今回の組み合わせは選択するかしないか，つまり，0と1で表現できます．
この特性を生かして全組み合わせをbitで表現することができます．
bin()では先頭に "0b" が付いた形で出力されるのでそこだけ注意しましょう.
n = 5 ans = [] for i in range(2**n): ans.append(bin(i)[2:].zfill(n)) print(ans)
これら三つの方法それぞれ出力の形式がリスト，タプル，文字列と異なりますが，似たような処理で扱うことができるので探索方法として紹介しました．
最後にどういった問題を解くことができるのか実際に解くことで解説していきたいと思います.
実践編
今回はAtCoderの問題:C-たくさんの数式を使っていきたいと思います．
問題文
1 以上 9 以下の数字のみからなる文字列Sが与えられます． この文字列の中で,あなたはこれら文字と文字の間のうち,いくつかの場所に + を入れることができます.一つも入れなくてもかまいません. ただし,+ が連続してはいけません.
このようにして出来る全ての文字列を数式とみなし,和を計算することができます.
ありうる全ての数式の値を計算し,その合計を出力してください.
制約
1≤|S|≤10
Sに含まれる文字は全て 1 〜 9 の数字
解答コード
S =input() ans_list = [] if len(S) == 1: print(int(S)) else: for i in range(2**(len(S)-1)): comb = bin(i)[2:].zfill(len(S)-1) num_list = [] num = S[0] for i in range(len(comb)): if comb[i] == "1": num_list.append(int(num)) num = S[i+1] else: num += S[i+1] num_list.append(int(num)) ans_list.append(sum(num_list)) print(sum(ans_list))
今回扱った問題では入力Sの間に"+"を入れるかどうかという組み合わせを列挙し，実際にその組み合わせによってできた数式を計算することで答えにたどり着くことができると思います．
ビットシフトの考え方を使うことでもっとコードを短く書くこともできますが，直感的な理解のためにこのような形で書いてみました．
コードを順番にさらっていけば理解できると思うのでもし扱った問題が解けなければ上記のコードを参考にしてみてください.
また，zfill()はゼロ埋めのことで
例えば，("1").zfill(3)としたら"001"となります．このように指定した文字列の長さにするために左側に0を埋めてくれます．
今回は部分集合をpythonでどう作るかということを解説してきました．
こんな方法が他にもあるよだったり，もっとこうした方が簡単だよというようなことがありましたら，コメントよろしくお願いします．
pythonでリストの要素をスペース区切りで出力をしたい時(メモ)
初めに
競技プログラミングに参加していると答えの入っているリストをスペースで区切って出力しろというような問題に当たることが多いと思います．
これまで私は" ".join(リスト)をよく使っていたのですが，より簡単な方法を見つけたので自身のメモ程度に載せておきたいと思います．
また，それ以外の方法もついでに載せておきます.
- 入力：n個の数字が入っているリスト
例：[1,2,…,n] - 出力例：n個の数字のそれぞれの間にスペースが入っている形の出力
例：1 2 3 4 … n
では，早速紹介していきたいと思います．
一番簡単な方法
リストに "*" を使ってアンパックし，それを出力するだけのもの．
入力:
x = [1,2,3,4,5] print(*x)
出力:
1 2 3 4 5
知っていれば一発で出力できるのでめっちゃ便利じゃないでしょうか？
汎用性が高い方法
" ".join(リスト)を使って，リストの中身をスペース区切りで出力する方法．スペース区切り以外にも",".join(リスト)とすることでカンマ区切りで出力することができたり汎用性が上記のものよりは高い.
入力:
x = [1,2,3,4,5] x = [str(i) for i in x] print(" ".join(x))
出力:
1 2 3 4 5
直感的にわかりやすい方法
pythonのprint()はその出力の完了時に改行(\n)が入力されています．その部分をスペース(" ")に変えてあげることでスペース区切りの出力をすることができます．
入力:
x = [1,2,3,4,5] for i in x: print(i, end=" ")
出力:
1 2 3 4 5
おまけ
リストの要素の数がすくなければこれでもいいとは思います．ただ今回紹介したものの方が簡単だと思うので一応できるということを示しておく程度に・・・
入力:
print(x[0],x[1],x[2],x[3],x[4])
出力:
1 2 3 4 5
最後に
今回はアスタリスク()でリストがアンパックできるということを知ったので紹介してみました．リストの頭にをつけるだけなので出力したい形がスペース区切りの時は使ってみてください．基本的には" ".join()が使いやすくておすすめです．
これ以外にも入出力の方法はあると思うので，また簡単な方法が見つかり次第追加したいと思います．
