パンケーキソート

パンケーキソートは、代わりに伝統的な並べ替え技術によって行われる比較の数を減らすの反転の数を減らすことに焦点を当てソートアルゴリズムです.
パンケーキを使ってパンケーキをひっくり返すようにパンケーキソートと呼ばれているので、配列をソートするためにできることはフリップ機能を使うことです.

パンケーキソートアルゴリズム

FF () :
Unsorted配列の先頭から、指定したインデックスまですべての値を反転します.

find_max():
ソートされていない配列の指定した範囲内の最大数のインデックスを探します.

<山縣>

繰り返し、配列のcurrentRangeサイズを減らします.配列がボトムアップ方法でソートされるという事実を知っています.

指定されたcurrentRangeサイズ内のソートされていない配列の最大値のインデックスを取得し、最大値のインデックスがcurrentRange - 1と等しくない場合にチェックします.

def flip(arr, i): 
    start = 0 
    while start < i: 
        arr[start], arr[i] = arr[i], arr[start]
        start += 1 
        i -= 1 

def find_max(arr, current_size): 
    mi = 0 
    for i in range(0, current_size): 
        if arr[i] > arr[mi]: 
            mi = i
    return mi 

def pancake_sort(arr): 
    current_size = len(arr) 
    while current_size > 1: 
        mi = find_max(arr, current_size)
        if mi != current_size - 1: 
            flip(arr, mi)
            flip(arr, current_size - 1)
        current_size -= 1
    return arr


arr = [40, 20, 28, 8, 60, 33]
print(pancake_sort(arr))

時間の複雑さ
複雑さ
値
ベスト
o ( n )
最悪
o ( n ^ 2 )