アセンブラCASL2でバブルソートを作ってみた

この記事では、アセンブラ言語で「バブルソート」について簡単な例題で学べます。
理解の助けになるように、シンプルな図解も用いております。また、アセンブラとアルゴリズムのの本の紹介もしています。

<<関連記事>>

基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和2年度(令和3年1月)合格報告

2020年からの基本情報技術者試験は、言語とアルゴリズムの配点が高くなりました。
なので、プログラミング未経験の事務員の私は、非常に焦っていましたが、無事合格できました。
学習中のアウトプットを少し編集してお届けしております。

シミュレーターと過去問を解くまでの勉強に使った参考書はこちらです
平成26年秋の過去問にバブルソートが出題されました。

疑似言語によるアルゴリズムをCASL2で再現してみたら、両方学べて
一石二鳥なのではと思い、今回は「バブルソート」を作ってみました。

配列BUBに「CBEAD」という文字が入っています。
これを「ABCDE」と並び替えます。
CASL2ではAは41、Bは42…という文字コードが割り当てられていて、
その大小で比較します。

バブルソートは、簡単に言うと、
「おケツから頭に向かって、お隣さん同士、どっちが大きいかを
比較するアルゴリズム」です。

まず、この図ですと、
AとDはDの方が大きいから、このまま。

EとAは、Eの方が大きいから交換

BとAはBの方が大きいから交換

CとAはCの方が大きいから交換

これで、先頭のAの場所が決定しました。

もう一度、配列のおケツから同じように
交換して、今度はBを確定していきます。
この時の頭をGR1、おケツから交換するアドレスをGR2

おケツと比較する位置をGR3、
GR2の値をGR4、GR3の値をGR5
値交換に使う作業領域をGR6(TEMPなどと呼ばれる)にします。

外ループでGR1である頭からの位置、
内ループでおケツから交換していくGR2が変わっていきます。

内ループはGR2がGR1より小さくなったら抜けて、
外ループはGR1が最後尾まで行ったら抜けます。
配列の最後尾の位置をGR7とします。

実行して見ます。

「CBEAD」と入力します。

並び替え前の配列が出力されます。

並び替え後の配列が出力されます。

以下プログラムになります。

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
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。

シミュレーターと過去問を解くまでの勉強に使った参考書はこちらです
平成26年秋の過去問にバブルソートが出題されました。

基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
これからプログラミングを始める方へ