Python でのクイックソート
-
Python でクイックソートするには
numpy.sort()メソッドを使用する -
Pandas ライブラリの
Series.sort_values()メソッドを用いた Python でのクイックソート - Python でのクイックソートの実装
このチュートリアルでは、Python での[クイックソートアルゴリズム](/ja/tutorial/algorithm/quick-sort/の実装と適用方法を説明します。
クイックソートは分割統治のアルゴリズムです。クイックソートは配列の中からピボットとして要素を選び、ピボットより小さい要素をある配列に、ピボットより大きい要素を別の配列に配置することで、選択したピボットを中心に配列を分割します。配列に重複した要素が含まれている場合、ピボットと等しい要素は、アルゴリズムの実装に応じて、3 番目の部分配列に入れるか、2つの部分配列のいずれかに入れることができます。配列は、再帰的な呼び出しによってサブアレイをソートすることで、クイックソートによってソートされます。
クイックソートアルゴリズムは要素を比較してソートするので、比較ソートアルゴリズムに属します。
Python でクイックソートするには numpy.sort() メソッドを使用する
numpy.sort(array, axis, kind) メソッドは配列を入力として受け取り、入力配列のソートされたコピーを出力として返します。パラメータ array はソートしたい配列、axis は配列をソートしたい方向、kind はメソッドが配列をソートする際に使用するアルゴリズムを指定します。
以下のサンプルコードは、numpy.sort() メソッドを用いて、Python でクイックソートを用いて配列をソートする方法を示しています。
import numpy as np
a = np.array([2, 3, 6, 5, 7, 8, 3, 1])
sorted_a = np.sort(a, kind="quick sort")
print(sorted_a)
出力：
[1 2 3 3 5 6 7 8]
Pandas ライブラリの Series.sort_values() メソッドを用いた Python でのクイックソート
Pandas ライブラリの Series.sort_values(ascending, inplace, kind) メソッドは Pandas の Series を入力として受け取り、ソートされた系列を返します。
引数 ascending のデフォルト値は True であり、このメソッドは系列を昇順にソートします。これが False に設定されている場合、Series は降順にソートされます。引数 inplace が True に設定されている場合、変更は元の系列で行われ、そうでない場合はソートされたコピーが返されます。そうでなければ、ソートされた入力のコピーが返されます。kind 引数は、どのアルゴリズムメソッドが系列のソートに用いるかを決定します。
以下の例では、Series.sortvalues() がどのようにしてクイックソートアルゴリズムを用いて Python で系列をソートするかを示しています。
import pandas as pd
s = pd.Series([1, 2, 4, 2, 7, 5, 3, 2, 6, 8])
s.sort_values(inplace=True, kind="quick sort")
print(s)
出力：
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Python でのクイックソートの実装
3つ目の方法は、Python で独自にクイックソートアルゴリズムを実装することです。
以下のコードでは、配列を 3つのサブアレイに分割しています。1つのサブアレイにはピボットよりも小さい要素、1つのサブアレイにはピボットよりも大きい要素、3つ目のサブアレイにはピボットと等しい要素が含まれています。
メソッドを呼び出すたびに、ピボットより小さい値とピボットより大きい値を分離しているので、ソートされたピボットの位置を取得します。そして、再帰的に呼び出すことで、ソートされた完全な配列を取得します。
以下のコード例は、Python で説明したクイックソートアルゴリズムを実装する方法を示しています。
def sort(array):
left = []
equal = []
right = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
left.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return (
sort(left) + equal + sort(greater)
) # recursive calling of the sort() function
else: # return the array, when it contains only 1 element
return array