データ構造とアルゴリズム：Qucikソート

重要度：高い!

インナー関数

関数の中であるまとまった処理を行う際に関数内に関数を定義することをインナー関数と呼ぶ。 関数内関数

コード

partionの部分で、pivotを配列の一番後ろの数値と決めて、その後左から一つづつpivotと比較して、pivotよりも小さければ一つ後ろの配列と入れ替える。その後右に移動して、pivotと比較して小さかったら入れ替える、大きかったらそのまま。というのを繰り返す。入れ替えを行う配列の要素はif numbers[j] <= pivot:でif文に引っかかった時はi += 1としているのでiの位置がどんどん右側にずれていく。if文に引っかかるたびにiの数値が大きくなり、交換する配列のindex番号が大きくなる。

最後に一番右に到達した後、移動していたiの番号の箇所にpivotの数値を入れる。 そうすることで下記のような状況が作れる。 - pivotの数字を挟んで - 右側はpivotより大きい数値 - 左側はpivotより小さい数値

最後に

_quick_sort(numbers, low, partition_index-1)
_quick_sort(numbers, partition_index+1, high)

の部分で再起呼び出しを行い、partition_index-1は配列の区切りの一つ前partition_index+1の部分で配列の区切りの一つ後を示し、それらの左右の部分で再度大きさを比較する_quick_sortを呼び出して、ソートが完了するまで同じ操作を行う。

from typing import List
import random

def partition(numbers: List[int], low: int, high: int) -> int:
    i = low - 1 
    pivot = numbers[high]
    for j in range(low, high):
        if numbers[j] <= pivot:
            i += 1
            numbers[i], numbers[j] = numbers[j], numbers[i]
    numbers[i+1], numbers[high] = numbers[high], numbers[i+1]
    return i+1

def quick_sort(numbers: List[int]) -> List[int]:
    def _quick_sort(numbers: List[int], low: int, high: int) -> None:
        if low < high:
            partition_index = partition(numbers, low, high)
            _quick_sort(numbers, low, partition_index-1)
            _quick_sort(numbers, partition_index+1, high)

    _quick_sort(numbers, 0, len(numbers)-1)
    return numbers

nums = [random.randint(0, 1000) for i in range(10)]
print(quick_sort(nums))

[37, 93, 174, 191, 218, 702, 813, 854, 951, 975]