ソートアルゴリズムについて
種類
- バブルソート
- マージソート
- クイックソート
- カウントソート
- 狭い範囲に数値があれば、かなり早い
バブルソート
-
概要
- 順繰りに交換したほうがいい場所をスキャンして交換する
- マージソートやクイックソートに比べてパフォーマンスが悪い
- 計算量
O(n^2)
- 視覚的な説明
コード
def bsort(arr):
n = len(arr)
for i in range(n-1):
for j in range(0, n-i-1):
# jとj+1が交換したほうがいい場合は交換
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
import random
arr = [random.randint(0, 100) for i in range(11)]
print(arr) # [66, 34, 62, 39, 31, 95, 89, 20, 53, 29, 5]
print(bsort(arr)) # [5, 20, 29, 31, 34, 39, 53, 62, 66, 89, 95]
google colab
マージソート
-
概要
- 再帰で小さい要素に分割し、小さい順に合成する方法
- 計算量
O(n log n)
- 視覚的な説明
コード
def msort(arr):
size = len(arr)
if size <= 1:
return
# 左右に分割してそれぞれソートする
middle = size // 2
left_arr, right_arr = arr[:middle], arr[middle:]
msort(left_arr)
msort(right_arr)
# 得られたleft_arr, right_arrを小さい順にマージしていく
# li: left index, ri: right index, ai: all index
li, ri, ai = 0, 0, 0
left_size, right_size = len(left_arr), len(right_arr)
while li < left_size and ri < right_size:
if left_arr[li] < right_arr[ri]:
arr[ai] = left_arr[li]
li += 1
else:
arr[ai] = right_arr[ri]
ri += 1
ai += 1
# 残りをarrに加える
while li < left_size:
arr[ai] = left_arr[li]
li += 1; ai += 1
while ri < right_size:
arr[ai] = right_arr[ri]
ri += 1; ai += 1
import random
arr = [random.randint(0, 100) for i in range(11)]
print(arr)
msort(arr)
print(arr)