クイックソート


クイックソートとは?


クイックソートは「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)