Bogoソート
平均的な計算時間はO((n+1)!)となっています。
非常に効率が悪く、安定ソートではない。
bogoの由来は「bogus(偽物)」からきているらしい。
配列をランダムに並び替えて配列の要素が左から順に小さくなっているかを都度調べていく。
運が良ければ早いし、最悪かなり時間がかかる。
def in_order(numbers: List[int]) -> bool:
return all(numbers[i] <= numbers[i + 1] for i in range(len(numbers) - 1))
def bogo_sort(numbers: List[int]) -> List[int]:
while not in_order(numbers):
random.shuffle(numbers)
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(bogo_sort(nums))
Bubbleソート
平均的な継続時間はO(n²)
隣り合う要素を比較しながら整列を行っていく。
アルゴリズムは単純ですが、効率が悪いのでBubbleソートを応用したものがよくつかわれる。
安定ソート
def bubble_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
for j in range(len_numbers - 1 - i): # ループ事に回数が減っていく
if numbers[j] > numbers[j + 1]: # 左のほうが大きかったら入れ替える
numbers[j], numbers[j + 1] = numbers[j + 1], numbers[j]
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(bubble_sort(nums))
cacktailソート(シェーカーソート)
Bubbleソートの改良版
Bubbleソートは一方向からのソートだったが、cactailソートは双方向からのソートになる。
平均的な継続時間はO(n²)安定ソート。
def cocktail_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
swapped = True
start = 0
end = len_numbers - 1
while swapped:
swapped = False
for i in range(start, end):
if numbers[i] > numbers[i + 1]:
numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
swapped = True
if not swapped:
break
swapped = False
end = end - 1
for i in range (end - 1, start - 1, -1): # 戻る時のソート
if numbers[i] > numbers[i + 1]:
numbers[i], numbers[i + 1] = numbers[i + 1], numbers[i]
swapped = True
start = start + 1
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(cocktail_sort(nums))
combソート(櫛ソート)
Bubbleソートの改良版。
平均的な継続時間は、ほぼO(n log n)になるが安定ソートではない。
配列の中身をn/1.3した間隔で整理し一通り行うと感覚を狭めて最終的に間隔が1になるまでおこなう。
1以降はswapがFalseになるまで行う。
def comb_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
gap = len_numbers
swapped = True
while gap != 1 or swapped:
gap = int (gap / 1.3)
if gap < 1:
gap = 1
swapped = False
for i in range(0, len_numbers - gap):
if numbers[i] > numbers[i + gap]:
numbers[i], numbers[i + gap] = numbers[i + gap], numbers[i]
swapped = True
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(comb_sort(nums))
selectionソート(選択ソート)
平均的な継続時間は、O(n2)になり安定ソートではない。
配列の一番最初から最小の数値を探し出し、最小値と最初の配列の中身を入れ替える。
同様に配列の末端まで行うことでソートされる。
計算量が遅いため配列が小さい時などに採用されることが多い
def selection_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(len_numbers):
min_index = i
for j in range(i + 1, len_numbers):
if numbers[min_index] > numbers[j]:
min_index = j
numbers[i], numbers[min_index] = numbers[min_index], numbers[i]
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(selection_sort(nums))
Gnomeソート
平均的な継続時間はO(n²)の安定ソート。
Bubbleソートの類似している。
左から順に隣接する値を比較していくが、正しければ次に移動するが、入れ替えた場合は1つ戻り値が正しい(比較)か確認をする。
def gnome_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
index = 0
while index < len_numbers:
if index == 0:
index += 1
if numbers[index] >= numbers[index - 1]:
index += 1
else:
numbers[index], numbers[index - 1] = numbers[index - 1], numbers[index]
index -= 1
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(gnome_sort(nums))
insertionソート
平均的な継続時間はO(n²)の安定ソート。
見る値を適切な位置に挿入するソート。
見る値をtempに保管しておき、tempとそのtempのindex前のものを比較して適切な位置に挿入する。
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > temp:
numbers[j + 1] = numbers[j]
j -= 1
numbers[j + 1] = temp
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(insertion_sort(nums))
Bucketソート
平均的な継続時間はO(n + k)の安定ソート
配列に対して事前にn種のバケツ(配列)を用意する。
配列の値をあるルールにそってバケツに追加していく。（コード上は値を配列サイズで割った商をもとにバケツに追加）
そのバケツをinsertionソートにかけて、バケツの中で順番を整えてresultの配列に追加していく。
def insertion_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
for i in range(1, len_numbers):
temp = numbers[i]
j = i - 1
while j >= 0 and numbers[j] > temp:
numbers[j + 1] = numbers[j]
j -= 1
numbers[j + 1] = temp
return numbers
def bucket_sort(numbers: List[int]) -> List[int]:
max_num = max(numbers)
len_numbers = len(numbers)
size = max_num // len_numbers
buckets = [[] for _ in range(size)]
for num in numbers:
i = num // size
if i != size:
buckets[i].append(num)
else:
buckets[size - 1].append(num)
for i in range(size):
insertion_sort(buckets[i])
result = []
for i in range(size):
result += buckets[i]
return result
nums = [random.randint(0, 1000) for _ in range(10)]
print(bucket_sort(nums))
shellソート
平均的な継続時間はO(n log n)の安定ソートではない。
shellソートは間隔を決めその間隔を狭めていくことで整列させる。
大まかに整列していくことが特徴的。
やり方自体はcombソートに近いが挿入ソート。
def shell_sort(numbers: List[int]) -> List[int]:
len_numbers = len(numbers)
gap = len_numbers // 2
while gap > 0:
for i in range(gap, len_numbers):
temp = numbers[i]
j = i
while j >= gap and numbers[j - gap] > temp:
numbers[j] = numbers[j - gap]
j -= gap
numbers[j] = temp
gap //= 2
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(shell_sort(nums))
countソート
平均的な継続時間はO(n)の安定ソート。
配列の最大値+1した空配列を用意する。
各要素の中身を空配列に何個あるか入れる。
何個あるかわかったら、自分と前の要素の数字を足す。
最終的にresultの配列へ最後尾の値をindex番号として取得し、result配列へ代入していく。
代入した際に、カウントした配列の要素を-1して、その後の同じ数字の時index番号が被らないようにする。
デメリットは配列要素の最大値+1分要素を準備しないといけないので、最大値が多ければ多いほど、メモリを食う。
def count_sort(numbers: List[int]) -> List[int]:
max_num = max(numbers)
counts = [0] * (max_num + 1)
result = [0] * len(numbers)
for num in numbers:
counts[num] += 1
for i in range(1, len(counts)):
counts[i] += counts[i - 1]
i = len(numbers) - 1
while i >= 0:
index = numbers[i]
result[counts[index] - 1] = numbers[i]
counts[index] -= 1
i -= 1
return result
nums = [random.randint(0, 1000) for _ in range(10)]
print(count_sort(nums))
radixソート
平均的な継続時間はO(n)で、安定ソート。
countソートを使用してradixソートは行われる。
radixソートは、配列の値を1の位から10の位と順番に整列させていく。
def count_sort(numbers: List[int], place: int) -> List[int]:
counts = [0] * 10
result = [0] * len(numbers)
for num in numbers:
index = int(num / place) % 10
counts[index] += 1
for i in range(1, 10):
counts[i] += counts[i - 1]
i = len(numbers) - 1
while i >= 0:
index = int(numbers[i] / place) % 10
result[counts[index] - 1] = numbers[i]
counts[index] -= 1
i -= 1
return result
def radix_sort(numbers: List[int]) -> List[int]:
max_num = max(numbers)
place = 1
while max_num > place:
numbers = count_sort(numbers, place)
place *= 10
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(radix_sort(nums))
quickソート
平均的な継続時間はO(n log n)で安定ソートではない。
ほかのソートよりも一般的に早いといわれているがデータの数や並びによってはO(n2)になる。
ピボットという適当な値を境界値として設定する。（コードでは末尾の値）
ピボット未満の値を左側に、以上の値を右側に集め、ピボットより左と右で再帰して再度ソートを行う。
def partition(numbers: List[int], low: int, high: int) -> int:
i = low - 1
pivod = numbers[high]
for j in range(low, high):
if numbers[j] <= pivod:
i += 1
numbers[i], numbers[j] = numbers[j], numbers[i]
numbers[i + 1], numbers[high] = numbers[high], numbers[i + 1]
return i + 1
def quick_sort(numbers: List[int]) -> List[int]:
def _quick_sort(numbers: List[int], low: int, high: int) -> None:
if low < high:
partition_index = partition(numbers, low, high)
_quick_sort(numbers, low, partition_index - 1)
_quick_sort(numbers, partition_index + 1, high)
_quick_sort(numbers, 0, len(numbers) - 1)
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(quick_sort(nums))
Mergeソート
平均的な継続時間はO(n log n)で安定ソート。
配列を中心から左右に分割する。
分割レベルが1の要素になるまで繰り返し行う。
分割し終えたら要素を順にマージしていく。
マージしていく際にソートを行い最終的にすべてマージされて完成。
[2,6,3,7,5,4,8,9]
[2,6,3,7] [5,4,8,9]
[2,6] [3,7] [5,4] [8,9]
[2] [6] [3] [7] [5] [4] [8] [9]
[2,6] [3,7] [4,5] [8,9]
[2, 3, 6, 7] [4, 5, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9]
def merge_sort(numbers: List[int]) -> List[int]:
if len(numbers) <= 1:
return numbers
center = len(numbers) // 2
left = numbers[:center]
right = numbers[center:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
numbers[k] = left[i]
i += 1
else:
numbers[k] = right[j]
j += 1
k += 1
while i < len(left):
numbers[k] = left[i]
i += 1
k += 1
while j < len(right):
numbers[k] = right[j]
j += 1
k += 1
return numbers
nums = [random.randint(0, 1000) for _ in range(10)]
print(merge_sort(nums))
まとめ
ソートquick, merge, bubble, selection, insertionあたりがよくつかわれる。
今時ソートなんてライブラリが充実してて学必要があるのか？という疑問もあります。
重要性を理解するというよりも、アルゴリズムの概念や考え方に触れることのほうがメリットが大きいように思います。
合わせて、ソートアルゴリズムの使い方や使いどころについて一緒に学んでいくとよりよいのかなと思いました。