Pythonでクイックソート
ウィキペディアにクイックソートのコードの例が載っていますが全く理解できませんでした。
自分で書いてみました。
def quick_sort(balls):
# 要素が1個以下の場合はそのまま返す。
if len(balls) <= 1 :
return balls
# 基準（先頭の要素）を決め、大小で要素を前半frontと後半rearに分ける。
front = [x for x in balls if x < balls[0]]
rear = [x for x in balls if x > balls[0]]
# 前半、基準、後半を一つのリストにまとめる。
return quick_sort(front) + [balls[0]] + quick_sort(rear)
# 要素が1個以下の場合はそのまま返す。
if len(balls) <= 1 :
return balls
# 基準（先頭の要素）を決め、大小で要素を前半frontと後半rearに分ける。
front = [x for x in balls if x < balls[0]]
rear = [x for x in balls if x > balls[0]]
# 前半、基準、後半を一つのリストにまとめる。
return quick_sort(front) + [balls[0]] + quick_sort(rear)
使い方は次のとおりです。
a = [5, 7, 12, 8, 4, 1, 9, 6, 2, 10, 3]
b = quick_sort(a)
print(b)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
b = quick_sort(a)
print(b)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
[ 2022年3月26日 | カテゴリー: Python | タグ: アルゴリズム , ソート ]
« パソコンがスリープ状態にならないようにする方法 | 頑固な文字化けを直すために試した方法 »
コメントを残す