ソートアルゴリズムのまとめと実装(Python)

はじめに

以下の本を読みながら、アルゴリズムの勉強を始めてます.

書籍では、C, C++の実装例が載っている.自分は、Pythonで実装してみた. 紹介するのは以下.

  • 挿入ソート
  • バブルソート
  • 選択ソート
  • マージソート
  • シェルソート
  • クイックソート

挿入ソート(Insertion Sort)

挿入ソート(インサーションソート)は、ソートのアルゴリズムの一つ。整列 してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計 算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、し ばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴ リズムであり、オンラインアルゴリズムである。

ALDS1_1_A

サンプル問題(AOJ): https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=jp

[sourcecode language=”python” title=”” ]
N = int(input())
A = list(map(int, input().split()))

def insertion_sort(A, N):
for i in range(1, N):
v = A[i]
j = i – 1
while j >= 0 and A[j] > v:
# vより大きければ右へずらす
A[j+1] = A[j]
j -= 1
A[j+1] = v
print(*A)

print(*A)
insertion_sort(A, N)
[/sourcecode]

バブルソート(Bubble Sort)

バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要 素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、ア ルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことか ら、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともい う。(単に交換法と言う場合もある)

ALDS1_2_A

サンプル問題(AOJ) https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A&lang=jp

[sourcecode language=”python” title=”” ]
N = int(input())
A = list(map(int, input().split()))

def bubble_sort(A, N):
cnt = 0
flag = True
while(flag):
flag = False
for i in range(N-1, 0, -1):
if(A[i-1] > A[i]):
A[i-1], A[i] = A[i], A[i-1]
cnt += 1
flag = True

print(” “.join(list(map(str, A))))
print(cnt)

bubble_sort(A, N)
[/sourcecode]

選択ソート(Selection Sort)

選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列さ れた要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをお こなうこと。最悪計算時間がO(n2)と遅いが、 アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。 後述するように、安定ソートではない。

ALDS1_2_B

サンプル問題(AOJ) https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B&lang=jp

↓のコード、どうしてもAOJ のテストケースを通せなかった。 どこかバグってるのだろうか??

[sourcecode language=”python” title=”” ]
def selection_sort(A, N):
count = 0
for i in range(0, N):
minj = i
for j in range(i, N):
if(A[minj] > A[j]):
minj = j
if(minj != i):
count += 1
A[minj], A[i] = A[i], A[minj]

print(” “.join(map(str, A)))
print(count)

N = int(input())
A = list(map(int, input().split()))
selection_sort(A, N)
[/sourcecode]

シェルソート(Shell Sort)

基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列され たデータに対しては高速」という特長があるものの、「隣り合った要素同士し か交換しない」ため、あまり整列されていないデータに対しては低速であった。

そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソート しておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適 用したのがシェルソートである。

ALDS1_2_D

サンプル問題(AOJ)

コード省略。解けない..

マージソート(Merge Sort)

分割統治法によるソート.

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列 も整列されている、というボトムアップの分割統治法による。大きい列を多数 の列に分割し、そのそれぞれをマージする作業は並列化できる。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分 割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレース なソートも提案されているが、通常O(n)の外部記憶を必要とする。

(ナイーブな)クイックソートと比べると、最悪計算量は少ない 。ランダムなデータでは通常、クイックソートのほうが速い。

ALDS1_5_B

サンプル問題(AOJ) https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp

[sourcecode language=”python” title=”” ]
def merge(A, left, mid, right):
global count
L = A[left:mid] + [1000000001]
R = A[mid:right] + [1000000001]
i = j = 0
for k in range(left, right):
if L[i] <= R[j]: A[k] = L[i] i += 1 else: A[k] = R[j] j += 1 count += right - left def merge_sort(A, left, right): if left + 1 < right: mid = (left + right) // 2 merge_sort(A, left, mid) merge_sort(A, mid, right) merge(A, left, mid, right) N = int(input()) A = list(map(int, input().split())) count = 0 merge_sort(A, 0, N) print(*A) print(count) [/sourcecode]

クイックソート(Quick Sort)

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発した ソートのアルゴリズム。分割統治法の一種。

最良計算量および平均計算量はO( nlog n )である。他のソート法と比べて、 一般的に最も高速だといわれているが対象のデータの並びやデータの数によっ ては必ずしも速いわけではなく、最悪の計算量はO( n^2)である。また数々 の変種がある。 安定ソートではない。

ALDS1_6_B, ALDS1_6_C

サンプル問題(AOJ) https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=jp https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C&lang=jp

[sourcecode language=”python” title=”” ]
def partition(a, p, r):
x = a[r][1]
i = p – 1
for j in range(p, r):
if a[j][1] <= x: i = i + 1 a[i], a[j] = a[j], a[i] a[i + 1], a[r] = a[r], a[i + 1] return i + 1 def quicksort(a, p, r): if p < r: q = partition(a, p, r) quicksort(a, p, q - 1) quicksort(a, q + 1, r) import sys n = int(input()) a = [] for i in range(n): suit, num = sys.stdin.readline().split() a += [[suit, int(num), i]] quicksort(a, 0, len(a) - 1) [/sourcecode]

Python 標準ライブラリ

リストオブジェクトに対する操作として、 sort()や, reverse()メソッドが用意されている.

[sourcecode language=”python” title=”” ]
listobj.sort()
listobj.reverce()
[/sourcecode]