Web備忘録

プログラミングを中心に技術的な事柄を忘れないように書き残します。

[Python] クイックソートの実装方法とアルゴリズム

Pythonとクイックソート Pythonでクイックソートを実装してみます。Python3.6を使います。 クイックソートは数あるソートアルゴリズムの中でも、実用上最速とされる誉れ高いアルゴリズムです。ただし条件次第で低速になってしまうので注意が必要です。 クイックソートは分割統治法と呼ばれる考え方を使ってソートを行います。まずソート対象のデータ(リスト)について、ピボット(基準値)を選び、その基準値より小さい値を前の方、大きい値を後ろの方に移動します。この ...

続きを読む ⇒

[Python] ヒープソートの実装方法とアルゴリズム

ヒープソートの実装方法とアルゴリズム Pythonでヒープソートを実装してみます。Python3.6を使います。 常に最大値(最小値)を取り出すことができるデータ構造があれば、それを使ってソートアルゴリズムが実装できるという考えのもと、考案されたのがヒープソートです。ソートは2分ヒープと呼ばれる木構造を使います。 2分ヒープは2分木で、子ノードが常に親ノードより小さいことが保障される木構造です。したがってルートノードが常に最大値となります。 ...

続きを読む ⇒

[Python] バブルソート/選択ソート/挿入ソートの速度比較

バブルソート/選択ソート/挿入ソートの速度比較 Pythonで作成した上記ソートアルゴリズムの実装を、処理速度の面から比較してみます。使用するコードは以下のページのものです。 [Python] バブルソートの実装方法とアルゴリズム [Python] 選択ソートの実装方法とアルゴリズム [Python] 挿入ソートの実装方法とアルゴリズム ソートアルゴリズムにはデータによって最良の時間計算量が期待できるものから、最悪の時間計算量 ...

続きを読む ⇒

[Python] 挿入ソートの実装方法とアルゴリズム

Pythonと選択ソート Pythonで挿入ソートを実装してみます。Python3.6を使います。 挿入ソートは、時間計算量 O(n^2) でバブルソートや選択ソートと同じく高速なソートアルゴリズムとは言えません。ただし、挿入ソートについて言えばある面で有用なソートアルゴリズムです。 挿入ソートは要素数の少ないデータに対して、高速に動作する可能性があります。これはクイックソートなど高速なソートアルゴリズムについては、処理のオーバーヘッドが発生するためです。 ...

続きを読む ⇒

[Python] 選択ソートの実装方法とアルゴリズム

Pythonと選択ソート Pythonの勉強Lv2で選択ソートを実装してみます。Python3.6を使います。選択ソートはバブルソートに次いで、単純で理解しやすいソートアルゴリズムです。 # 選択ソート def selection_sort(array): n = len(array) for i in range(0, n-1): # 最小値のインデックスを保持 min = i for j in r ...

続きを読む ⇒