はじめに
皆さん2020年あけましておめでとうございます。ryuichi69と申します。
本日もアルゴリズムの練習のアウトプット、説明の練習がてらこの文章を書きました。正直分かりやすく書くのが大変で、説明の分かりにくい部分、要件漏れ等がありましたらご連絡下さい。
クイックソート
概要
まずソートとは、配列の要素を昇順または降順に並び替える事を言います。
ソートの方法は何種類もありますが、そのうちクイックソートとは、配列の基準値を起点として、それより大きいものの配列、小さいものの配列に小分けにしていって行ってソートしていく手法です。
クイックソートの例
例えば配列a=[5,6,3,1,8]があり、これを昇順にクイックソートする事を考えます。さらに配列内の中央値を基準値とします。
ここで配列aの要素の中央値は3ですね。この3を境目に3より小さい要素を下の青、3より大きい要素を下の黄色のように、半分に2分割していきます。さらに下の図の2回目の分割のように、再帰的に配列を半分に分割していき、配列の要素数が1つになった時点で再帰を打ち切ります。最後に１つの配列に統合して完成です。
ここで実装の手順をまとめると、
実装の手順
- 配列a[i]の要素eの中央値m(基準値)を探します。
- 分割後の配列の要素数が1個になったら、再帰を打ち切る処理を書く(再帰の停止条件)。
- 配列の各要素elementごとに。a[i] < mの場合はelementを配列left、a[i] > mの場合はelementを配列rightに値を格納します。
- 配列left、配列rightに対し上記1～2を再帰的に実行します。
例題
nを自然数、iを0≦i≦(n-1)を満たす整数とする。このときクイックソートにより、n個の要素を持つ配列a[i]を昇順にソートせよ。
制約
- 1≦n≦10
- 1≦a[i]≦10
入力
a = [7,3,10,5,9,1,6,4,8,2]
出力
[1,2,3,4,5,6,7,8,9,10]
プログラム
ソースコードは、@suecharoさんの「ソートアルゴリズムと Python での実装 - Qiita」のクイックソートのものベースとしています。配列を2つに分けてソートする点が分からなかったので、カンニングさせて頂きました。
quickSort.py
import os
import statistics
def quickSort(arr):
# 配列のメジアンより小さい要素を集めた配列
left = []
# 配列のメジアンより大きい要素を集めた配列
right = []
# 再帰の停止条件
# 再帰的に配列を分割した後の、要素数が1以下になったら停止する
if len(arr) <= 1:
return arr
# 配列の中央値(メジアン)を取得する
median = int(statistics.median(arr))
# 配列内に含まれる中央値の個数を数えるための変数
medianFlg = 0
for element in arr:
# 配列の要素(element)が中央値より小さいので、
# 配列leftに値を格納する
if element < median:
left.append(element)
# 配列の要素(element)が中央値より大きいので、
# 配列rightに値を格納する
elif element > median:
right.append(element)
else:
# elementが配列の中央値の場合は、
# 返り値に加える中央値の個数分だけ、フラグに+1し続ける
medianFlg += 1
# 配列がどのように分割されているかを確かめたい場合は、
# このタイミングでprintで確認すると良い
# print(left)
# print(right)
# 配列left、配列right毎に再帰を行い
# 配列を小さな配列に区切る
left = quickSort(left)
right = quickSort(right)
# 配列left、中央値の[median]、配列rightを結合したものを返す
return left + [median] * medianFlg + right
# テスト用
if __name__ == "__main__":
print(quickSort([7,3,10,5,9,1,6,4,8,2]))