sedでバブルソート (超簡略版)

先にこんなものを書きました:

sedで足し算(超簡略版)

sedで掛け算(超簡略版)

これらの超簡略版と同じく、1から9の1桁の数字の並びをsedでバブルソートしてみます。

まずは、食わせるデータ:

2 1 3 9 8 6 7 5 4

これをbsort.datとします。中身はいろいろ変えて試してみて下さい。

では、sedのコードです。bsort.sedとします。なお、きちんとデバッグをしてないので (というか一発書きなので。hとxのみマニュアル参照しました)、単純なミス、および論理的なミスが入っているかもしれません。その点、ご承知おきください。

# -*- coding:utf-8 -*-
s/(.+)( *)/\1 /g
p
:loop
s/(.+) \+/\1 /
h
s/.*/===>/
p
x
/2 1/ {
    s/2 1/1 2/
    s/(.*) (\**)/\1 \*/
    p
}
/3 1/ {
    s/3 1/1 3/
    s/(.*) (\**)/\1 \*/
    p
}
/4 1/ {
    s/4 1/1 4/
    s/(.*) (\**)/\1 \*/
    p
}
/5 1/ {
    s/5 1/1 5/
    s/(.*) (\**)/\1 \*/
    p
}
/6 1/ {
    s/6 1/1 6/
    s/(.*) (\**)/\1 \*/
    p
}
/7 1/ {
    s/7 1/1 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 1/ {
    s/8 1/1 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 1/ {
    s/9 1/1 9/
    s/(.*) (\**)/\1 \*/
    p
}
/3 2/ {
    s/3 2/2 3/
    s/(.*) (\**)/\1 \*/
    p
}
/4 2/ {
    s/4 2/2 4/
    s/(.*) (\**)/\1 \*/
    p
}
/5 2/ {
    s/5 2/2 5/
    s/(.*) (\**)/\1 \*/
    p
}
/6 2/ {
    s/6 2/2 6/
    s/(.*) (\**)/\1 \*/
    p
}
/7 2/ {
    s/7 2/2 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 2/ {
    s/8 2/2 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 2/ {
    s/9 2/2 9/
    s/(.*) (\**)/\1 \*/
    p
}
/4 3/ {
    s/4 3/3 4/
    s/(.*) (\**)/\1 \*/
    p
}
/5 3/ {
    s/5 3/3 5/
    s/(.*) (\**)/\1 \*/
    p
}
/6 3/ {
    s/6 3/3 6/
    s/(.*) (\**)/\1 \*/
    p
}
/7 3/ {
    s/7 3/3 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 3/ {
    s/8 3/3 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 3/ {
    s/9 3/3 9/
    s/(.*) (\**)/\1 \*/
    p
}
/5 4/ {
    s/5 4/4 5/
    s/(.*) (\**)/\1 \*/
    p
}
/6 4/ {
    s/6 4/4 6/
    s/(.*) (\**)/\1 \*/
    p
}
/7 4/ {
    s/7 4/4 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 4/ {
    s/8 4/4 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 4/ {
    s/9 4/4 9/
    s/(.*) (\**)/\1 \*/
    p
}
/6 5/ {
    s/6 5/5 6/
    s/(.*) (\**)/\1 \*/
    p
}
/7 5/ {
    s/7 5/5 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 5/ {
    s/8 5/5 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 5/ {
    s/9 5/5 9/
    s/(.*) (\**)/\1 \*/
    p
}
/7 6/ {
    s/7 6/6 7/
    s/(.*) (\**)/\1 \*/
    p
}
/8 6/ {
    s/8 6/6 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 6/ {
    s/9 6/6 9/
    s/(.*) (\**)/\1 \*/
    p
}
/8 7/ {
    s/8 7/7 8/
    s/(.*) (\**)/\1 \*/
    p
}
/9 7/ {
    s/9 7/7 9/
    s/(.*) (\**)/\1 \*/
    p
}
/9 8/ {
    s/9 8/8 9/
    s/(.*) (\**)/\1 \*/
    p
}
/\*$/ {
    p
    s/\*$/\+/
    bloop
}
p

では、実行してみます。

$sed -r -f bsort.sed bsort.dat
2 1 3 9 8 6 7 5 4 
===>
1 2 3 9 8 6 7 5 4 *
1 2 3 9 8 6 7 4 5 *
1 2 3 9 8 6 4 7 5 *
1 2 3 9 8 6 4 5 7 *
1 2 3 9 6 8 4 5 7 *
1 2 3 6 9 8 4 5 7 *
1 2 3 6 8 9 4 5 7 *
1 2 3 6 8 9 4 5 7 *
===>
1 2 3 6 8 4 9 5 7 *
1 2 3 6 8 4 5 9 7 *
1 2 3 6 8 4 5 7 9 *
1 2 3 6 8 4 5 7 9 *
===>
1 2 3 6 4 8 5 7 9 *
1 2 3 6 4 5 8 7 9 *
1 2 3 6 4 5 7 8 9 *
1 2 3 6 4 5 7 8 9 *
===>
1 2 3 4 6 5 7 8 9 *
1 2 3 4 5 6 7 8 9 *
1 2 3 4 5 6 7 8 9 *
===>
1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 
  
===>

行の末尾に * がついているのは、入れ換えが行なわれたことを示しています。どこの入れ換えが行なわれたかは示していませんが、上の行あたりと見比べると、わかると思います。なお、すべての ===> の上2行は同じ内容になっているはずですが、これは ===> の上の1行が /\*$/ のブロック内の p による出力であるためです。

最後から2つめの ===> のところでは、末尾に * がついていません。これは入れ換えが行なわれなかったことを示します。入れ換えのループ全体を繰り返すかどうかを、末尾の * の有無で判定しています。ありなら繰り返す、なしなら終わります。なお、末尾に * がついていても、下から3つめの ===> のところのように、ソートが完了している場合があります。場合があるというか、この下から3つめという位置で、ソートは完了しているはずです。ですので、このコードでは1回無駄にループを回るようになっています。これは、 * というマーカを、入れ換えが行なわれた場合に付加し、その上でその有無によってループをもう一回するかどうかを決めているという方法によるものです。

とりあえず書いただけなので、あらゆる種類のバグが入っている可能性がありますが、見つけたらそこをフィックスして遊んでみて下さい。また、このコードでは上に述べたように1回無駄にループを回ります (実際には出力をみるとわかるようにもう1回、計2回無駄に回っています)。この無駄をなくすにはどうしたらいいかを考えてみるのも面白いと思います。

なお、コードの上のほうに hと x という命令が書いてあります。sedには、普通に処理の対象となるpattern spaceと、それとは別になにかデータを置いておけるhold spaceという領域があります。このコードでは ===> を表示させるために、処理中の対象をhold spaceに退避させ、pattern spaceに ===> を置き、それを表示させています。その後にhold spaceから処理中の対象を x にてpattern spaceに復帰させています。

追記 (重要) Apr 16, 2019:

このstoryはあくまでパズルです。

この辺りからチューリング・マシンに話を繋げていきたいとは考えていますが、構想の段階です。

kuzu/NULL