この記事では、アセンブラ言語で「バブルソート」について簡単な例題で学べます。
理解の助けになるように、シンプルな図解も用いております。また、アセンブラとアルゴリズムのの本の紹介もしています。
<<関連記事>>
基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和2年度(令和3年1月)合格報告
2020年からの基本情報技術者試験は、言語とアルゴリズムの配点が高くなりました。
なので、プログラミング未経験の事務員の私は、非常に焦っていましたが、無事合格できました。
学習中のアウトプットを少し編集してお届けしております。
シミュレーターと過去問を解くまでの勉強に使った参考書はこちらです
平成26年秋の過去問にバブルソートが出題されました。
疑似言語によるアルゴリズムをCASL2で再現してみたら、両方学べて
一石二鳥なのではと思い、今回は「バブルソート」を作ってみました。
配列BUBに「CBEAD」という文字が入っています。
これを「ABCDE」と並び替えます。
CASL2ではAは41、Bは42…という文字コードが割り当てられていて、
その大小で比較します。
バブルソートは、簡単に言うと、
「おケツから頭に向かって、お隣さん同士、どっちが大きいかを
比較するアルゴリズム」です。
まず、この図ですと、
AとDはDの方が大きいから、このまま。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ1.png)
EとAは、Eの方が大きいから交換
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ2.png)
BとAはBの方が大きいから交換
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ3.png)
CとAはCの方が大きいから交換
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ4.png)
これで、先頭のAの場所が決定しました。
もう一度、配列のおケツから同じように
交換して、今度はBを確定していきます。
この時の頭をGR1、おケツから交換するアドレスをGR2
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ5.png)
おケツと比較する位置をGR3、
GR2の値をGR4、GR3の値をGR5
値交換に使う作業領域をGR6(TEMPなどと呼ばれる)にします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ6.png)
外ループでGR1である頭からの位置、
内ループでおケツから交換していくGR2が変わっていきます。
内ループはGR2がGR1より小さくなったら抜けて、
外ループはGR1が最後尾まで行ったら抜けます。
配列の最後尾の位置をGR7とします。
実行して見ます。
「CBEAD」と入力します。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ7.png)
並び替え前の配列が出力されます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ8.png)
並び替え後の配列が出力されます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ9.png)
以下プログラムになります。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/バブ10.png)
TEST START
RPUSH
IN BUB,LEN
OUT BUB,LEN
LAD GR7,BUB
ADDA GR7,=4
LAD GR1,BUB
LOOP1
LAD GR2,BUB
ADDA GR2,=4
LOOP2 LD GR3,GR2
SUBA GR3,=1
LD GR4,0,GR2
LD GR5,0,GR3
CPA GR4,GR5
JMI KOUKAN
JUMP SHORI
KOUKAN LD GR6,GR4
LD GR4,GR5
LD GR5,GR6
ST GR4,0,GR2
ST GR5,0,GR3
SHORI LAD GR2,-1,GR2
CPA GR2,GR1
JPL LOOP2
LAD GR1,1,GR1
CPA GR1,GR7
JMI LOOP1
OUT BUB,LEN
RPOP
RET
BUB DS 5
LEN DC 5
END
ご精読ありがとうございました。
この記事を書くのに勉強になった本を紹介します。
多分この記事を読んで面白かったと思われた方は、
きっとハマると思います。
◆アルゴリズム問題がちゃんと解ける本
アルゴリズム学習の定番。
アルゴリズムが苦手で何とかしたい方におススメ
◆アルゴリズムはじめの一歩完全攻略
実際に作って学べます。
Javaを使っています。
私はJava初めてでしたが、
それでも、ハッシュ関数の所までは、
どうにかついていけました。
もっと頑張ります。
◆速習言語CASL2
CASL2、何それ、テーマパークの絶叫マシーン
みたいな名前だね、ぐらいだった私でも、入門書として楽しく読めた本です。
◆プログラミング入門CASL2
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。