マージソートアルゴリズムのバグ修正
マージソート アルゴリズムで数値リストを並べ替えるプログラムが与えられています。merge_sort() 関数をテストしたところ、コードが正しくありません。正しく動作するようにアルゴリズムを修正できますか？
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
演習の手順
- 左半分を代入する際の誤りを修正します。
- 右半分を代入する際の誤りを修正します。
- 左半分のポインタを更新する際の誤りを修正します。
- 右半分のポインタを更新する際の誤りを修正します。
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def merge_sort(my_list):
if len(my_list) > 1:
mid = len(my_list)//2
left_half = my_list[:mid]
right_half = my_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
# Correct mistake when assigning left half
my_list[k] = right_half[i]
i += 1
else:
# Correct mistake when assigning right half
my_list[k] = left_half[j]
j += 1
k += 1
while i < len(left_half):
my_list[k] = left_half[i]
# Correct mistake when updating pointer for left half
j += 1
k += 1
while j < len(right_half):
my_list[k] = right_half[j]
# Correct mistake when updating pointer for right half
i += 1
k += 1
my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)