Bashでバブルソートを実装する: 番兵を使って効率化

作成日: 2020-08-31
更新日: 2023-12-24
カテゴリ: Bash

Bashでバブルソート

Bashスクリプトでバブルソートを実装してみました。
ソースコードは↓です。

# ソート対象の配列  
arr=(2 3 1 4)  

# ループ用のフラグ  
loop=1;  

# 番兵カウンター  
k=0  

while [ $loop -ne 0 ]; do  
    # フラグを折る  
    ((loop=0))  

    for ((i=0; i<${#arr[@]} - 1 - k; i++)); do  
        # iの要素がi+1より大きい？  
        if [ ${arr[i]} -gt ${arr[i + 1]} ]; then  
            # 要素のスワップ  
            ((tmp = arr[i]));  
            ((arr[i] = arr[i + 1]));  
            ((arr[i + 1] = tmp));  

            # フラグを立てる  
            ((loop = 1));  
        fi  
    done  

    # 番兵カウンターをカウント  
    ((k++))  
done  

# 結果を出力  
echo ${arr[@]}

バブルソートとは？

バブルソートとはソートアルゴリズムのひとつです。

バブルソート - Wikipedia

ソートとはデータの集まりを一定の規則で並べ替える処理のことを指します。
たとえばランダムに並んだ数列があります。

2 3 1 4

この数列を小さい順に並べ替えると

1 2 3 4

このようになります。これがソートです。

ソートはデータの下処理によく使われます。
たとえばバイナリーサーチではソート済みの配列を前提としています。
他にもデータを見やすくするなどの効果もあります。

バブルソートの仕組み

バブルソートは配列の先頭から隣り合う要素を比較し、隣の要素が隣要素より大きければ（あるいは小さければ）、その要素同士をスワップ（交換）します。
このスワップを配列が整列するまで繰り返すのがバブルソートです。
ソートされていく様子がバブルのように見えることからこのような名前が付きました。

バブルソートの実装の詳細

さきほどのバブルソートのコードを解説します。

ソート対象の配列

最初にソート対象の配列を定義しておきます。
Bashではカッコの中に値を書くと配列を作ることができます。

# ソート対象の配列  
arr=(2 3 1 4)

ループ用のフラグ

ループ用のフラグを用意します。
今回のバブルソートでは、ループを2つ使います。

# ループ用のフラグ  
loop=1;

番兵カウンター

番兵カウンターを定義します。
バブルソートの特徴としてソートを続けると配列の後方の要素から順々に整列されていくようになります。
つまりソート中ではその整列済みの要素に対しては処理を実行しなくていいことになります。
この番兵カウンターはソート済みの要素数分、ループ回数を減算するためのカウンタです。
ループ回数をこの番兵で減算することで後方の要素に対しての処理を省略しています。

# 番兵カウンター  
k=0

ループ1つ目

1つ目のループに入るとすぐにフラグを折ります。
このフラグは配列の要素のスワップが発生すると再び立てられます。

while [ $loop -ne 0 ]; do  
    # フラグを折る  
    ((loop=0))  

    ...  
done

ループ2つ目

ネストされた2つ目のループです。
ループは配列の先頭から処理していきます。
配列の末尾の要素に関しては、比較する要素が無いため省略してもいいことになります。よって-1しています。
あとは配列の要素数から番兵カウンター分を減算すれば、処理すべき要素数がわかります。

    for ((i=0; i<${#arr[@]} - 1 - k; i++)); do  
        ...  
    done

隣り合う要素の比較

「i番目の要素がi+1番目の要素より大きければ」というif文を書きます。
このif文が要素をスワップする条件です。
昇順にソートしたい場合は-gt, 降順にソートしたい場合は-ltにします。

        if [ ${arr[i]} -gt ${arr[i + 1]} ]; then  
            ...  
        fi

要素のスワップ

if文のブロック内では実際に要素をスワップします。
スワップはtmpという変数にi番目の要素を避難し、i番目の要素にi+1番目の要素を代入します。
i+1番目の要素にはさきほどの避難したtmpを代入します。
これでスワップ完了です。

スワップが完了したらループ用のフラグを立てます。
スワップが発生するということは、まだ配列全体が整列されてないということです。
よってフラグを立てて次のスワップを発生させます。

            # 要素のスワップ  
            ((tmp = arr[i]));  
            ((arr[i] = arr[i + 1]));  
            ((arr[i + 1] = tmp));  

            # フラグを立てる  
            ((loop = 1));

番兵カウンターのカウント

最後にwhile文の末尾で番兵カウンターをカウントします。

while [ $loop -ne 0 ]; do  
    ...  

    # 番兵カウンターをカウント  
    ((k++))  
done

出力結果

バブルソートの実行結果です。
配列が昇順にソートされました。

1 2 3 4

ユーニックス総合研究所