アルゴリズム練習

クイックソート

pivot(基準値)を中心に、より小さな値とより大きな値を並べます.
pivotを基準に区分してパーティションと呼ぶ.DivideとConquerのDivideフェーズ.
pivotの両側にそれぞれ1つの値があるか、値がないまで再帰的に繰り返す.

実際のクイックソートの分割手順は次のとおりです.
先頭のインデックスから、基準値と値を比較し、bとiのインデックスを移動します.
比較値が大きいほど、iのみが移動します.逆に、b、iはインデックスを交換しながら移動します.
上記の操作を繰り返し、iは最後にbとpivotの位置を変更する.

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    my_list[index1],my_list[index2] = my_list[index2],my_list[index1]
    return my_list
    
# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    p = end
    b = start
    i = start
    
    while i < p:
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, b, i)
            b += 1
        i += 1
    swap_elements(my_list, b, p)
    p = b
    return p

partition関数が完了したら、その上でクイックソートを実行します.

# 퀵 정렬
def quicksort(my_list, start=0, end=None):
    if end is None:
        end = len(my_list)-1
        
    if end - start < 1 :
        return
        
    p = partition(my_list, start, end)
    
    quicksort(my_list, start, p-1)
    quicksort(my_list, p+1, end)    
    return
    
    # 내가 착각해서 잘못 구현했던 부분
    # left_list = my_list[:p]
    # right_list = my_list[p+1:]
    # quicksort(left_list, start, len(left_list)-1)
    # quicksort(right_list, start, len(right_list)-1)

最初の実装では、既存のリストをleft listとright listに分け、再帰的な高速ソートを再実行します.これは、最初のリストでソートを実行するのではなく、各リストが異なるように実行し、エラーの結果を生成します.

# 정답
[1, 5, 7, 9, 13, 15, 28, 30, 48]
# 오답
[13, 9, 1, 5, 7, 15, 30, 28, 48]

上記のエラーの答えのように、partitionに分割された各リストのみをソートし、リスト全体をソートしません.高速ソートは、関数が新しいリストを生成せずにソートされるため、これを反映する必要があります.