クイックソートとは?

クイックソートは「quick」の名前からもわかり、処理速度が速いソートアルゴリズムです.このソートは、多くのデータをソートするためによく使用されます.有名なソートアルゴリズムの中でも、実際に使用する頻度が最も高い最も重要なアルゴリズムです.
クイックソートは、「標準値を選択した後、より小さなデータ・グループとより大きなデータ・グループに分けます.」これは、このような処理を繰り返し実行することによってデータをソートするアルゴリズムである.

クイックソートは、2つの処理で構成されます。

は

を処理し、標準値を境界としてデータをサイズに分割する

に分割するデータに対して同じ動作を繰り返す

.

下図に示すように、クイックソートを実行できます.

コード実装

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)