from typing import List
def bubble_sort(nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(n-i-1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
print(bubble_sort([6, 15, 4, 2, 8])) # Output: [2, 4, 6, 8, 15]
from typing import List
def merge(nums: List[int], left: int, mid: int, right: int):
# 並べ替えられた左右の半分を一時配列にコピー
left_nums = nums[left:mid+1]
right_nums = nums[mid+1:right+1]
i, j, k = 0, 0, left # left_nums、right_nums、numsのインデックス
# 二つの並べ替えられた半分を元の配列に統合
while i < len(left_nums) and j < len(right_nums):
if left_nums[i] <= right_nums[j]:
nums[k] = left_nums[i]
i += 1
else:
nums[k] = right_nums[j]
j += 1
k += 1
# left_numsとright_numsの残りの要素をコピー(あれば)
while i < len(left_nums):
nums[k] = left_nums[i]
i += 1
k += 1
while j < len(right_nums):
nums[k] = right_nums[j]
j += 1
k += 1
def merge_sort(nums: List[int], left: int, right: int) -> List[int]:
# これ以上分割できない場合
if left >= right:
return nums
# 配列の中間インデックス
mid = (left + right) // 2
# 左右の半分を再帰的に並べ替え
merge_sort(nums, left, mid)
merge_sort(nums, mid+1, right)
# 並べ替えられた半分を統合
merge(nums, left, mid, right)
return nums
print(merge_sort([5, 2, 3, 2, 1], 0, 4))
from typing import List
import random
def partition(nums: List[int], left: int, right: int):
# Pivotをランダムに選択する
pivot_index = random.randint(left, right)
pivot_value = nums[pivot_index]
# Pivotをリストの最後に移動する
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
i = left
# リストをパーティションに分ける
for j in range(left, right):
if nums[j] < pivot_value:
nums[i], nums[j] = nums[j], nums[i]
i += 1
# Pivotを正しい位置に移動する
nums[i], nums[right] = nums[right], nums[i]
return i # Pivotの位置を返す
def quick_sort(nums: List[int], left: int, right: int):
if left >= right:
return
mid = partition(nums, left, right)
quick_sort(nums, left, mid-1)
quick_sort(nums, mid+1, right)
nums = [5, 2, 1, 4, 3]
quick_sort(nums, 0, len(nums)-1)
print(nums) # Output: [1, 2, 3, 4, 5]