【第4回】ソート問題：クイックソート

問題
ヒント
1. ヒント１：クイックソートとは
2. ヒント２：ロジックの考え方
答え

問題

｛5, 10, 7, 8, 3, 1, 9, 2｝の数値配列を昇順にソートするプログラムを作りなさい。
ソート方法はクイックソートを使いなさい。

そもそもクイックソートがわからない方はヒント１を参照してください。
なるべくヒント２以降見ないように、自力で解いてください。

ヒント

ヒント１：クイックソートとは

閾値は数字配列にある数字ならどれでもいいのですが、
今回は数字配列の真ん中の数字でクイックソートを行います。

引用：http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/quick-sort.html

上記のようにクイックソートは閾値まで
左からは大きい値、右からは小さい値を探して値を交換していきます。
閾値にたどり着くと、そこから右配列、左配列に分かれて
同様に値交換をしていきます。

これは配列の数が多くなれば多くなるほど複雑になっていきます。

ヒント２：ロジックの考え方

①if分岐：すでに比べた値を重複して比べないIF分を作る
閾値を設定する
左カーソル位置を設定
右カーソル位置を設定
ループ処理：左のカーソル位置が右のカーソル位置と交差しない間処理を繰り返す
ループ処理：左カーソル値が閾値より大きい値がない間、カーソル位置を右にずらしていく
ループ処理：右カーソル値が閾値より小さい値がない間、カーソル位置を左にずらしていく
if分岐：すでに比べた値を重複して比べないIF分を作る
左カーソルの値と右カーソルの値を交換する
左カーソル位置を右にずらす
右カーソル位置を左にずらす
閾値位置より左側の配列を切り分けして「①if分岐」からの処理を行う
閾値位置より右側の配列を切り分けして「①if分岐」からの処理を行う

答え

arr = [5, 10, 7, 8, 3, 1, 9, 2]

def quick_sort(array): # 関数を作る
    left = [] # 基準値より小さい数字を込むリスト
    right = [] # 基準値より大きい数字を込むリスト
    
    if len(array) <= 1:  # 再帰関数を終わるための条件
        return array
    
    p = array[0] # 配列の中の数字を比較するための数字をpという変数で決める
    
    for i in range(1, len(array)): # 配列の数字をｐを基準して小さい数はleft、大きい数はrightに込むための反復門
        if p > array[i]:
            left.append(array[i])
        else:
            right.append(array[i])
    
    return quick_sort(left) + [p] +  quick_sort(right) # 再帰反復門を使って関数を継続に進めて、最後に整理できた数字を集める

print(quick_sort(arr))

arr = [5, 10, 7, 8, 3, 1, 9, 2]

def quick_sort(array): # 関数を作る

left = [] # 基準値より小さい数字を込むリスト

right = [] # 基準値より大きい数字を込むリスト

if len(array) <= 1: # 再帰関数を終わるための条件

return array

p = array[0] # 配列の中の数字を比較するための数字をpという変数で決める

for i in range(1, len(array)): # 配列の数字をｐを基準して小さい数はleft、大きい数はrightに込むための反復門

if p > array[i]:

left.append(array[i])

else:

right.append(array[i])

return quick_sort(left) + [p] + quick_sort(right) # 再帰反復門を使って関数を継続に進めて、最後に整理できた数字を集める

print(quick_sort(arr))