アルゴリズムの基礎: クイックソート
クイックソート
フローチャートは、以下の本を参考に作成しました。
丁寧な解説は上記の本など参考してもらうとして、 クイックソートの基本方針は以下のとおりです。
- 手前から基準値よりも大きい値をさがす
- 後ろから基準値よりも小さい値をさがす
- それらを交換する
フローチャート
上記の基本方針をもとに、実行されています。 また、最後に基準値を正しい場所に移動する処理も追加しています。
import random
N = 9
# get random array
arr = list(range(1, N+1))
random.shuffle(arr)
print("inital array: {0}".format(arr))
# initial value
left = 0
right = N -1
def quick_sort(arr, left, right):
i = left + 1
k = right
_ref_value = arr[left] # reference value
_tmp = None
print("start: left={0}, right={1}, arr[left:right+1]={2}".format(left, right, arr[left:right+1]))
print("\t _ref_value={0}".format(_ref_value))
while (i < k):
# looking for a value bigger than _ref_value
while (arr[i] < _ref_value and i < right):
i = i + 1
# looking for a value smaller than _ref_value
while (arr[k] >= _ref_value and left < k):
k = k - 1
if (i < k):
print("\t i={0}, arr[i]={1}, k={2}, arr[k]={3}".format(i, arr[i], k, arr[k]))
_tmp = arr[i]
arr[i] = arr[k]
arr[k] = _tmp
# replace refrence value
if (arr[left] > arr[k]):
_tmp = arr[left]
arr[left] = arr[k]
arr[k] = _tmp
print("\t left={0}, arr[left] = {1}, k={2}, arr[k]={3}".format(left, arr[left], k, arr[k]))
print("\t result: {0}".format(arr))
quick_sort(arr, left, right)
以下、実行例です。 実行すると、基準値5を境にして、[3,4,1,2], [5], [7,8,9,6]のようにソートされます。
inital array: [5, 4, 8, 7, 3, 2, 1, 9, 6] start: left=0, right=8, arr[left:right+1]=[5, 4, 8, 7, 3, 2, 1, 9, 6] _ref_value=5 i=2, arr[i]=8, k=6, arr[k]=1 i=3, arr[i]=7, k=5, arr[k]=2 left=0, arr[left] = 3, k=4, arr[k]=5 result: [3, 4, 1, 2, 5, 7, 8, 9, 6]
最後にarr[k]に基準値を入れています。 そのため、以下の図のようになっています。
- [left, k-1]は基準値よりも小さい値の配列
- kの位置には実行時に決定された基準値
- [k+1, right]は基準値よりも大きい値の配列
しかし、基準値以外は正しく順番にソートされていません。 残りの部分に対して、正しくソートするために、再び[left, k-1]および[k+1, right]の 配列に対して、上記の操作を再帰的に行う必要があります。
再帰的に実行
quick_sort()を再帰的に実行して、全体をソートします。 以下のフローチャートにて、オレンジ部分が新たに追加した箇所です。
このように再帰的に呼び出しを行うことで、配列のすべての値が正しくソートされるようになります。
pythonでの実装例を示します。
import random
N = 9
# get random array
arr = list(range(1, N+1))
random.shuffle(arr)
print("inital array: {0}".format(arr))
# initial value
left = 0
right = N -1
def quick_sort(arr, left, right):
i = left + 1
k = right
_ref_value = arr[left] # reference value
_tmp = None
print("start: left={0}, right={1}, arr[left:right+1]={2}".format(left, right, arr[left:right+1]))
print("\t _ref_value={0}".format(_ref_value))
while (i < k):
# looking for a value bigger than _ref_value
while (arr[i] < _ref_value and i < right):
i = i + 1
# looking for a value smaller than _ref_value
while (arr[k] >= _ref_value and left < k):
k = k - 1
if (i < k):
print("\t i={0}, arr[i]={1}, k={2}, arr[k]={3}".format(i, arr[i], k, arr[k]))
_tmp = arr[i]
arr[i] = arr[k]
arr[k] = _tmp
# replace refrence value
if (arr[left] > arr[k]):
_tmp = arr[left]
arr[left] = arr[k]
arr[k] = _tmp
print("\t left={0}, arr[left] = {1}, k={2}, arr[k]={3}".format(left, arr[left], k, arr[k]))
print("\t result: {0}".format(arr))
# call quick_sort() recursively
if (left < k - 1):
quick_sort(arr, left, k - 1)
if (k + 1 < right):
quick_sort(arr, k + 1, right)
quick_sort(arr, left, right)
以下に実行結果の一例です。
inital array: [7, 4, 9, 2, 5, 6, 1, 3, 8] start: left=0, right=8, arr[left:right+1]=[7, 4, 9, 2, 5, 6, 1, 3, 8] _ref_value=7 i=2, arr[i]=9, k=7, arr[k]=3 left=0, arr[left] = 1, k=6, arr[k]=7 result: [1, 4, 3, 2, 5, 6, 7, 9, 8] start: left=0, right=5, arr[left:right+1]=[1, 4, 3, 2, 5, 6] _ref_value=1 result: [1, 4, 3, 2, 5, 6, 7, 9, 8] start: left=1, right=5, arr[left:right+1]=[4, 3, 2, 5, 6] _ref_value=4 left=1, arr[left] = 2, k=3, arr[k]=4 result: [1, 2, 3, 4, 5, 6, 7, 9, 8] start: left=1, right=2, arr[left:right+1]=[2, 3] _ref_value=2 result: [1, 2, 3, 4, 5, 6, 7, 9, 8] start: left=4, right=5, arr[left:right+1]=[5, 6] _ref_value=5 result: [1, 2, 3, 4, 5, 6, 7, 9, 8] start: left=7, right=8, arr[left:right+1]=[9, 8] _ref_value=9 left=7, arr[left] = 8, k=8, arr[k]=9 result: [1, 2, 3, 4, 5, 6, 7, 8, 9]
今後は、実際にpostgresqlでのクイックそーその実装部分に関して勉強して記事にしたいです。
