シェーカーソートの実装 python

前回、配列の１方向スキャンを繰り返して前後の配列の大小を比較してひたすら並び替えていくアルゴリズム（バブルソート）について考えました。

今回は、そのバブルソートを若干効率化したシェーカーソートを実装してみます。

シェーカーソートとは

バブルソートが１方向に走査するのに対して、シェーカーソートでは最後のスワップ位置を記録しておき、そこから逆方向に向かって走査を繰り返していくことで整列済みの無駄な配列を再スキャンすることなくソーティングすることができます。

実装

シンプルなアルゴリズムなので、早速実装していきます。

import random
class Seq:
    def __init__(self,n) -> None:
        self.seq = [i+1 for i in range(n)]
    def set(self):
        return random.sample(self.seq,len(self.seq))
def is_not_sorted(seq):
    for i in range(len(seq)-1):
        if seq[i]>seq[i+1]:
            return True
        else:
            pass
    return False

seq = Seq(200)
seq = seq.set()

def shaker_sort(seq):
    start_loc = 0
    k =0
    while is_not_sorted(seq) :
        if k%2 == 0:
            seq = seq[::-1]
            for i in range(start_loc,len(seq)-1):
                if seq[i]>seq[i+1]:
                    seq[i],seq[i+1]=seq[i+1],seq[i]
                    end_loc = i
            start_loc = len(seq)-end_loc-1
        elif k%2 !=0:
            seq = seq[::-1]
            for i in range(start_loc,len(seq)-1):
                if seq[i]<seq[i+1]:
                    seq[i],seq[i+1]=seq[i+1],seq[i]
                    end_loc = i
            start_loc = len(seq)-end_loc-1
            
        k+=1
    if k %2 !=0:
        return seq
    else:
        return seq[::-1]

バブルソートと違い、逆方向スキャンを考慮してスキャン回数kに応じて配列をフリップします。