データ構造とアルゴリズム：cocktail（シェーカーソート）

cocktail（シェイクソート）

カクテルをシェークするような動きをするのでこのような名前がつけられている。bubbleソートの改良版でbubbleソートにかなり類似しておりbubbleソートを振る、ようなイメージ。

まず、左から右に配列を見ていって小さければ入れ替え、というのはbubbleソートの時と同様。 ただ、swap = Falseというフラグがあり、その周回の時に入れ替えが起きたらSwapをTrueに変更する。一番右のlimitまできたらswapをFalseに直して、今度は右から左に数字を見る。

この時に左の方が大きければ、右と入れ替える。という作業を行う。一番大きい数値は最初の段階で一番右にくるのでlimitを一つ下げる。

右から左に来るときは、一番左の数値が一番小さい数値になるので左側のlimitを一つ上げるようにする。

一度もswapがTrueにならなかったらその時点でソートを完了して良い。そのため、swapが Trueにならない周回があったらその時点でソートが完了しているとみなしても良いため、全てのパターンを行う必要がなくBubbleソートよりも早く処理が完了する。

• まずswapの初期値がTrueなのでwhile swappedの箇所でwhilteのloopに入る。
• 通常のbubbleソート同様に左の数値が大きければ右の数値と入れ替えるというのを１重のfor文で実現する
• ①の最後でもしswappが起こればswappedフラグをTrueにする。
  • この時点で、swappedがFalseのままであれば、その時点でソート完了し、breakとなる
  • 初期でendを−１している理由は、最初のfor文で一番後ろに最大値が移動するので一番後ろまで処理する必要がないから
• そのご②に入る
  • ②に入る前にend - 1をしてあげることで、limitを一つずらす
• for i in range(end-1, start-1, -1):というfor文は配列を逆順に入れる作業をしている
  • この逆順にする作業で、for文を逆から読み込ませる作業を行なっている。実際に行っているのは通常のbubbleソートの逆順にしたバージョンである。
  • 最後にもしswapped = Trueになれば再度一番上に戻り①からやり直しswapped = Falseのまま続くまで行う。

from typing import List

def cocktail_sort(numbers: List[int]) -> List[int]:
    len_numbers = len(numbers)
    swapped = True
    start = 0
    end = len_numbers - 1
    
    while swapped:
        swapped = False
        # 右方向に進むときの for loop
        # for①=============================start
        for i in range(start, end):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True
        # for①=============================end
        
        # swappが変更されなければfalseのままなのでここで処理が終了
        if not swapped:
            break

        swapped = False
        end = end - 1
        
        # for②=============================start
        for i in range(end-1, start-1, -1):
            if numbers[i] > numbers[i+1]:
                numbers[i], numbers[i+1] = numbers[i+1], numbers[i]
                swapped = True
        # for②=============================end
        start = start + 1
    
    return numbers


import random
arry = [random.randint(0, 100) for i in range(10)]
print(cocktail_sort(arry))


[0, 5, 36, 44, 53, 55, 68, 83, 84, 96]

このサイトのgif?がすごくわかりやすいのだが、右に行くときは大きいものを一番右に押しやる作業、左に行くときは小さいものを一番左に押しやる作業を行なっているのがわかる。 眺めていられるシェーカーソートのシミュレーション|JavaScript