ソートアルゴリズム：シェーカーソートとは

ソートアルゴリズムとは

ソートアルゴリズムの意味は、ソートとアルゴリズムの意味を理解すれば分かります。

ソートとは、ある規則に則って、データを並び替えることを指します。

アルゴリズムは、ある課題に対してどのように解決するのかその方法や考え方を指します。

したがって、ソートアルゴリズムとは、バラバラのデータを規則的にどのように並び替えるのかという考え方のことです。

その中の１つであるシェーカーソートを紹介します。

今回は、バラバラの数値データを昇順に並び替えることを考えます。

シェーカーソートとは

シェーカーソートとは、バブルソートを改良したアルゴリズムになります。

バブルソートのについてはこちらの記事を参照してください。

2021年9月26日ソートアルゴリズム：バブルソートとは

バブルソートでは、値を隣と比較して、昇順に並び替えます。シェーカーソートも変わりません。

しかし、シェーカーソートでは、小さい値、大きい値と交互にソートしていきます。

バブルソートでは、片側方向から比較しましたが、シェーカーソートでは、往復しながら比較することになります。

プログラムで書いてみよう

Pythonでシェーカーソートのプログラムを書いてみようと思います。

バブルソートと基本的には変わりません。下のプログラムはバブルソートのプログラムですが、一方向(要素番号が小さい方から大きい方)に比較しています。

def shaker(data):
    length=len(data)
    for i in range(1,length):
        for j in range(length-i):
            if data[j]>data[j+1]:
                data[j],data[j+1] = data[j+1],data[j]
    return data

繰り返し処理の中に、2方向から比較するため、２つの繰り返し処理をします。

for j in range(length-i)では、大きい値をfor k in range(length-i,i-1,-1)では、小さい値を決定しています。

def shaker(data):
    length=len(data)
    for i in range(1,length):
        for j in range(length-i):
            if data[j]>data[j+1]:
                data[j],data[j+1] = data[j+1],data[j]
        for k in range(length-1,i-1,-1):
            if data[k]<data[k-1]:
                data[k],data[k-1] = data[k-1],data[k]
    return data

ですが、このままだと同じ事を2重にしてしまっているので、繰り返し処理を更に編集します。

def shaker(data):
    length=len(data)
    for i in range(1,length):
        for j in range(i,length-i):
            if data[j]>data[j+1]:
                data[j],data[j+1] = data[j+1],data[j]
        for k in range(length-i,i-1,-1):
            if data[k]<data[k-1]:
                data[k],data[k-1] = data[k-1],data[k]
    return data

data=[5,4,3,2,1]
print(data)
cdata=shaker(data)
print(cdata)

range関数の中に変数iを入れることで2重に同じ処理をするのを防ぎます。

いざ、実行。