Python3で配列をクイックソートする

はじめに

皆さん2020年あけましておめでとうございます。ryuichi69と申します。
本日もアルゴリズムの練習のアウトプット、説明の練習がてらこの文章を書きました。正直分かりやすく書くのが大変で、説明の分かりにくい部分、要件漏れ等がありましたらご連絡下さい。

クイックソート

概要

まずソートとは、配列の要素を昇順または降順に並び替える事を言います。

ソートの方法は何種類もありますが、そのうちクイックソートとは、配列の基準値を起点として、それより大きいものの配列、小さいものの配列に小分けにしていって行ってソートしていく手法です。

クイックソートの例

例えば配列a=[5,6,3,1,8]があり、これを昇順にクイックソートする事を考えます。さらに配列内の中央値を基準値とします。

ここで配列aの要素の中央値は3ですね。この3を境目に3より小さい要素を下の青、3より大きい要素を下の黄色のように、半分に2分割していきます。さらに下の図の2回目の分割のように、再帰的に配列を半分に分割していき、配列の要素数が1つになった時点で再帰を打ち切ります。最後に１つの配列に統合して完成です。

ここで実装の手順をまとめると、

実装の手順

1. 配列a[i]の要素eの中央値m(基準値)を探します。
2. 分割後の配列の要素数が1個になったら、再帰を打ち切る処理を書く(再帰の停止条件)。
3. 配列の各要素elementごとに。a[i] < mの場合はelementを配列left、a[i] > mの場合はelementを配列rightに値を格納します。
4. 配列left、配列rightに対し上記1～2を再帰的に実行します。

例題

nを自然数、iを0≦i≦(n-1)を満たす整数とする。このときクイックソートにより、n個の要素を持つ配列a[i]を昇順にソートせよ。

制約

1. 1≦n≦10
2. 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]))