クイックソートアルゴリズムの実装
この演習では、クイックソートアルゴリズムを実装して数値のリストを並べ替えます。
最初のステップでは、partition() 関数を実装します。この関数は、処理後にピボットの左側の要素がすべてピボットより小さく、右側の要素がすべてピボットより大きくなるようにリストを並べ替えたうえで、ピボットのインデックスを返します。
次のステップでは、partition() 関数を呼び出す quicksort() 関数を実装します。
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def partition(my_list, first_index, last_index):
pivot = my_list[first_index]
left_pointer = first_index + 1
right_pointer = last_index
while True:
# Iterate until the value pointed by left_pointer is greater than pivot or left_pointer is greater than last_index
while ____ < ____ and ____ < ____:
left_pointer += 1
while my_list[right_pointer] > pivot and right_pointer >= first_index:
right_pointer -= 1
if left_pointer >= right_pointer:
break
# Swap the values for the elements located at the left_pointer and right_pointer
my_list[left_pointer], my_list[right_pointer] = ____, ____
my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]
return right_pointer