0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

クイックソート|大きい順

Posted at

#クイックソートを実装する

最初に「26」を基準の数(ピボット)とする。
「26」より大きい物をLeftへ
「26」より小さい物をRightへセットする。
左と右に分けられるので
それぞれ分けられたリストを同様の処理をしていく。
Left[32, 65, 76, 43, 87, 59]
Right[13, 22, 14]

次にLeftがソーティングされますがピボットは先頭の「32」です。
これを繰り返すことで下の結果の通りになります。

QuickSort.py
data = [26,13,32,65,76,22,43,87,14,59]

def QuickSort(data):
    if len(data) <= 1: # データが1個以下ならそのまま値を戻す
        return data

    # 基準となるデータ(ピボット)としてリストの先頭の値を使用
    pivot = data[0]
    left, right, same = [], [], 0 # 初期化(リスト、リスト、0)

    for ii in data:
        if ii > pivot:
            left.append(ii)  # ピボットより大きい場合、左側へセット
        elif ii < pivot:
            right.append(ii) # ピボットより小さい場合、右側へセット
        else:
            same += 1        # 同じ値は移動せず、数だけカウント

    left  = QuickSort(left)  # 左側のソート
    right = QuickSort(right) # 右側のソート
    # ソート済みデータとピボットとを合わせて返す
    return left + [pivot] * same + right

print(QuickSort(data))

# 結果
# [87, 76, 65, 59, 43, 32, 26, 22, 14, 13]

「分割統治法」っという言い方もあるようですが、小さい単位に分割を繰り返して処理を再帰的に繰り返します。
ピボットの選び方次第で処理は速くもなればいろいろあるようです。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?