pythonでバケットソートの実装してみた
バケットソート(計数ソート)
pythonでは可変長の配列を作り出すことが簡単にできるのでバケットソートに関しては今まで学んだ知識を使わずに実装することができます．
今回扱うバケットソートには, 大きく分けて2種類の実装があります．
まずひとつは,可変個の要素を保持できるデータ構造を使ってバケツを表現する方法です．pythonのリストの考え方で言うと数値の種類分の二次元配列を用意し,その中にデータを入れていく方法です．
もうひとつは,いったん整列対象のデータを走査して値ごとの出現回数を数えておき,その出現回数に従った数値をリスト化する方法です．
この実装によるバケットソートのみを指して特に分布数えソート，計数ソート(Counting Sort)などと言うそうです．(参照)
バケットソートの実装
今回は後者の計数ソートの形をpythonで実装していきたいと思います．
import random def counting_sort(A, max_num): #配列は0スタートのため count_list = [0]*(max_num+1) for i in A: count_list[i] += 1 i = 0 for num in range(len(count_list)): for c in range(count_list[num]): A[i] = num i += 1 #要素数15の配列を作成 A = [random.randint(1,10) for _ in range(15)] #randomに生成できる整数の最大値をmax_numとしてsortしていく print(A) counting_sort(A, 10) print(A)
出力例
[9, 3, 8, 3, 6, 7, 6, 4, 8, 5, 9, 8, 2, 2, 2] [2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 9]
pythonのリストを利用するとメモリを動的に増やすことができるのでバケットソートに関してはマージソート，クイックソートと比べると簡単に実装することができますね．
メモリの確保をしないといけないので要素数の数にだけ注意が必要になります．
pythonでアルファベットのリストの出力
先日受けたアルゴリズム実技検定でアルファベットのリストを作成してそれを利用するような問題が出ていたので自身の備忘録も兼ねてアルファベットのリストの作成方法をまとめました．
基本的にはqiita記事を参考にしているので元記事が気になる人はこちらを見てください．
コード例
まず，コピペ用にアルファベットの全ての小文字を出力する三つのコード例を載せておきます．
import string print(list(string.ascii_lowercase))
print([chr(ord("a")+i) for i in range(26)])
print([chr(i) for i in range(97, 97+26)])
出力はいずれも下記のようになっています．
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
stringを使った方法
pythonの標準ライブラリのstringを使った方法です．stringではアルファベット以外にも特殊文字や数字に関しても扱うことができます．文字列で出力されるのでlist()でリスト化すれば，アルファベットのリストが手に入ります．
ここでは，stringを使って何を出力できるのかコードとその出力を載せておきたいと思います．
import string #アルファベットの大文字小文字の出力 print(string.ascii_letters) #アルファベットの小文字のみの出力 print(string.ascii_lowercase) #アルファベットの大文字のみの出力 print(string.ascii_uppercase) #数値の文字列の出力 print(string.digits) #16進数で扱う文字列の出力 print(string.hexdigits) #８進法で扱う文字列の出力 print(string.octdigits) #特殊文字列の出力 print(string.punctuation) #上記で扱った文字列の出力 print(string.printable) #スペースや改行など空白に関する文字列の出力 print(string.whitespace)
出力(printableとwhitespace以外に関して)
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789 0123456789abcdefABCDEF 01234567 !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
chrを使った方法
PythonでUnicodeコードポイント（文字コード）の文字列を返してくれるのがchr()です.
ある一文字に対応するUnicodeコードポイントを表す整数値を返してくれるのがord()です．
#chrとordの関係性 print(chr(49)) # "1" print(ord("1")) # 49
この関係性を使うことでアルファベットのリストを出力することができます．
# upper-case A-Z print([chr(i) for i in range(65,65+26)]) print([chr(ord("A")+i) for i in range(26)]) # lower-case a-z print([chr(i) for i in range(97,97+26)]) print([chr(ord("a")+i) for i in range(26)])
競技プログラミングなどでたまにリストを用意しておく必要があるので，今後すぐに見られるようにメモとして記事にしました．
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 "
残りのコード部分に関しては
という処理を行なっているだけです．
パーティションの実装ができ，再帰関数の扱い方に慣れていれば意外と簡単に実装できますね．
もっとこんな実装があるよとかこれを実装してみて欲しいというようなものがあればコメントください！
第三回 アルゴリズム実技検定に参加してみた
こんにちは，今回はAtCoder社が提供しているアルゴリズム実技検定が無料で開催されていたので受けてみた感想に関して話していきたいと思います．
アルゴリズム実技検定とは
アルゴリズムの実装力をエントリー，初級，中級，上級，エキスパートの5段階で評価する検定になります．
有効期間は2年だそうですが，まだ検定としての力はそこまでないと思うので仕事で競プロに近いことをしている人や就活で競プロに関して話したい人は一度受けてみるといいかもしれませんね．
問題の内容に関しては普段のABCやAGCに近いものになっていて競技プログラミング経験者にとっては難なく解き始めることができると思います．もし受験してみたいという方がいましたら先に過去問が解けるようになっているので解いてみてから参加してみるといいと思います．
結果はどうだったのか
自分の検定結果に関しては…
46点で初級でした
期限が近かったこともあり昨日の夜から一気にやっていたのですが，途中で力尽きてしまいました.
受験者の分布はこんな感じらしいです．
検定終了後にこういった証明書がもらえるのはとても嬉しかったです．
問題に関して
自分がやっていた問題までの所感ですが，A~F問題まではアルゴリズムに関してはそこまで問われておらず，基本を抑えていて問題文をちゃんと理解すれば実装できるレベルだと感じました．
ABCだとC問題まで解ければこの辺までは解けるのではないかなと思います．
G~は基本的なアルゴリズムを抑えていれば解けるかなぁという感じでした．G, Hに関してはABCのD問題ぐらいの難易度な感覚でした．
もっと後半の問題に関してはまだ見れてないので復習する時に記事の更新をするかもしれません．
総評
5時間の制限時間があることと提出にペナルティがないことから普段より時間をかけてじっくり解くことができるので時間があればできそうだったのにというような状態にはあまりならないところがいいなと思いました．
自分は時間足りなくて悔しい思いをしましたが…
普段コンテストに参加できない人に証明できるものを用意するために作られた検定なので時間がなくいつもコンテストに参加できない人にはとてもいいものだと感じました．
5時間ぶっ通しでコードを書くのは少し疲れましたが楽しかったです．
また機会があったら参加してみたいと思います！
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の要素群の値の大小を群の先頭から順に比較しています．
一連の処理を終えると出力例の最終行のようにソートされた値が並ぶと思います．
