Pythonのクイックソートのサンプル
Pythonのクイックソートのサンプルコード
def quick_sort(arr): # arrが空か、1つの要素しかない場合は、そのまま返す if len(arr) <= 1: return arr # 基準値を決める pivot = arr[0] # 基準値より小さい要素を格納する配列 left = [] # 基準値より大きい要素を格納する配列 right = [] # 基準値を除いた要素を左右に分ける for i in range(1, len(arr)): if arr[i] < pivot: left.append(arr[i]) else: right.append(arr[i]) # 左右の要素を再帰的にクイックソートする left = quick_sort(left) right = quick_sort(right) # 左右の要素と基準値を結合して、結果を返す return left + [pivot] + right # クイックソートを実行する arr = [3, 5, 1, 2, 6, 4] print(quick_sort(arr)) # [1, 2, 3, 4, 5, 6]
コードを実行するとこうなります。
[1, 2, 3, 4, 5, 6]
上記のコードでは、基準値を配列の先頭から決めています。実際には、任意の要素を基準値として使用することもできます。また、このコードは、配列が昇順で並んでいる場合に最適な動作をしますが、降順の場合や、ランダムな並びの場合には効率が悪くなる可能性があります。
さらに、上記のコードでは、再帰的にクイックソートを実行していますが、再帰的にない実装も可能です。また、上記のコードでは、クイックソートを実行するための関数だけを記述していますが、実際には、その関数を使用するプログラム全体を記述する必要があります。
Pythonのクイックソートのアルゴリズム解説
上記のコードを見ながら、クイックソートのアルゴリズムを見ていきましょう。
まず、quick_sort()関数が定義されています。この関数は、引数として与えられた配列をクイックソートして、その結果を返します。
配列が空か、要素が1つしかない場合は、そのまま返すようにしています。これは、クイックソートが成立するための前提条件です。
次に、基準値を決めます。このサンプルコードでは、配列の先頭から基準値を決めています。
基準値より小さい要素を格納する配列 left と、基準値より大きい要素を格納する配列 right を定義します。
そして、基準値を除いた配列をfor文を使って巡回します。各要素が基準値より小さいか、大きいかを判定し、それぞれ left と right に追加します。
左側と右側の要素それぞれを再帰的にクイックソートするようにしています。これにより、左側と右側の要素をそれぞれ昇順に並び替えます。
最後に、左側、基準値、右側を結合して、結果を返します。これにより、全体として昇順に並び替えられた配列が返されます。
最後に、上記の関数を使用して、クイックソートを実行するプログラム例が示されています。このプログラムでは、配列 arr を作成し、それをクイックソートするようにしています。
実行すると、配列 arr の要素が昇順に並び替えられた状態で出力されます。
このように、Pythonでクイックソートを実装することができます。
改良を加えるなら、例えば、基準値を選ぶ方法を工夫することで、降順やランダムな配列でもより効率的な処理が可能になります。また、再帰的な実装の他に、再帰を使用しない実装も可能です。
さらに、実際には、クイックソートを行うプログラム全体を記述する必要があります。そのため、入力の受け取り方や、結果の出力方法など、さらなる改良が必要となるでしょう。
また、ソートのような処理は、exe化することで高速化が見込めます。
関連 pythonのexe化
Pythonのクイックソートは、組み込みライブラリsortedでも実現できる
Pythonには組み込みの関数 sorted() があります。この関数は、与えられた配列を昇順に並び替えることができます。また、この関数は、配列の内容が昇順である場合には、高速に動作する実装を使用します。
ただし、この関数は、配列が降順やランダムな並びの場合には、効率が悪くなる可能性があります。また、この関数は、配列を昇順に並び替えるだけであり、任意の順序に並び替えることはできません。
sortedを使ったサンプルコードはこう。ソート対象のデータサイズが小さいときは差がわからないので、100万件のデータの昇順と降順の実行時間を表示するようにしてみました。
$ cat quick.py
#!/usr/bin/python3
import time
import random
# 100万個の要素を持つ配列を作成する
arr = [i for i in range(1000000)]
# 配列をランダムに並び替える
random.shuffle(arr)
# 配列を昇順に並び替える
start = time.time()
sorted_arr = sorted(arr)
end = time.time()
print("昇順ソート実行時間: ", end - start)
# 配列を降順に並び替える
start = time.time()
sorted_arr = sorted(arr, reverse=True)
end = time.time()
print("降順実行時間: ", end - start)
実行するとこうなります。
$ ./quick.py 昇順ソート実行時間: 1.0260288715362549 降順実行時間: 1.0419926643371582
100万件でも、0.02秒程度の差。相当な巨大データをソートする場合でなければ、気にしなくていいのかも。上記は、Intel Coreの2CPU（2.13GHz）の古いパソコンで実行した結果です。
Pythonのクイックソートのまとめ
- Pythonのクイックソートは、関数定義して再帰的呼び出しすることで実装が可能
- 組み込み関数sortedを使っての実装が簡単。しかし、昇順以外のソートは効率が悪くなる
- しかし、100万件のソートでも0.02秒程度の差なのでデータ量によっては気にしなくて良いかも。