この記事では、アセンブラ言語で「挿入法」について簡単な例題で学べます。
シンプルな図解を用いています。また、アセンブラの本の紹介もしています。
挿入法について、別名「ぶち込み法」と命名しました(=^x^=)
<<関連記事>>
基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和2年(令和3年1月)合格報告
2020年からの基本情報技術者試験は、言語とアルゴリズムの配点が高くなりました。
なので、プログラミング未経験の事務員の私は、非常に焦っていましたが、無事合格できました。
学習中のアウトプットを少し編集してお届けしております。
疑似言語によるアルゴリズムをCASL2で再現してみたら、両方学べて
一石二鳥なのではと思い、今回は「挿入法」を作ってみました。
気づいたことですが、
挿入法って「ぶち込み法」だと思うと、
分かりやすいのかもしれないです。
挿入法は、既に整列済みの範囲の中に、
今見ている値を適切な位置に順々にぶち込んで行きます。
配列DATAに、「CBEAD」と入力します。
これを「ABCDE」に揃えます。
CASL2では文字コードで大小を判断して、
例えばAなら41、Bなら42…と比較して探します。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/1-3.png)
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/2-3.png)
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/3-3.png)
この例で行くと、
既に整列済みのCに対して、
今GR1で見ているBをぶち込みます。
この時、GR2で指す範囲は、
配列の先頭の要素0から、GR1より1つ前までです。
GR1が右に進んでいくほど、GR2の動ける範囲が
多くなります。
Bを作業領域(TEMP)のGR3に
退避します。
その後、ループのフラグを「true」にします。
フラグはGR4で示します。
配列DATAの先頭アドレス(固定)をGR5に設定します。
配列DATAの末尾のアドレス(固定)をGR6に設定します。
GR2が指す値をGR7に設定します。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/4-3.png)
CとBで、Cの方が大きいなので、
Cを1つ右にどかすイメージでコピーします。
GR2を1つ前に移動させます。
GR2が配列の先頭より前になったので、
ループを抜けます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/5-3.png)
GR3に退避したBを、
Cがあった所にぶち込むイメージでコピーします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/6-2.png)
最初のループ修了では、こうなりました。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/7-1.png)
これで、要素0にB、要素1にCが来て整列済みになりました。
次はEを要素2のEをぶち込む処理をします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/8-1.png)
GR1は要素2のEを指し、GR2は、要素1~要素0の
範囲で動きます。
EはGR3に退避させます。
フラグはtrueです。
CはEより小さいので、
GR4のフラグを「False」にしてループを抜けます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/9.png)
次は要素3のAを処理します。
GR3にAを退避させます。
ループのフラグをtrueにします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/10.png)
要素3のAを整列済みのBCDの適切な位置にぶち込んでいきます。
EとAを比べて、Eの方が大きいので、Eを1つ後ろにどかすイメージで
コピーします。
GR2を1つ前に移動させます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/11.png)
次に、AとCでは、Cの方が大きいので、Cを1後ろに
どかすイメージでコピーします。
GR2を1つ前に移動させます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/12.png)
次に、AとBでは、Bの方が大きいので、Bを1後ろに
どかすイメージでコピーします。
GR2を1つ前に移動させます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/13.png)
GR2が配列の先頭より前になったので、ループを抜けます。
GR3に退避したAを要素0にぶち込みます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/14.png)
最後にDをぶち込む処理をします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/15.png)
GR3にDを退避させます。
EとDではEの方が大きいので、
Eを右にどかすイメージでコピーします。
GR2を1つ前にします。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/16.png)
次に、CとDを比較します。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/17.png)
Cの方が小さいので、フラグをFalseにして、
ループを抜けます。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/18.png)
Dをぶち込むイメージでコピーします。
これで整列が完了しました。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/19.png)
出力結果になります。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/20.png)
プログラミングです。
![](https://nekosiestr77.xsrv.jp/wp-content/uploads/2020/06/21.png)
TEST START
RPUSH
IN DATA,LEN
OUT DATA,LEN
LAD GR1,DATA
LAD GR1,1,GR1 ;挿入する要素は要素1から
LAD GR5,DATA ;先頭アドレス(固定)
LD GR6,GR5 ;末尾のアドレス(固定)
LAD GR6,4,GR6
LOOP1 CPA GR1,GR6
JPL FIN
LD GR3,0,GR1 ;挿入する要素をTEMPへ退避
LD GR2,GR1 ;整列済み領域アドレスの設定
SUBA GR2,=1
LD GR4,=’true’ ;ループフラグの設定
LOOP2 CPA GR2,GR5 ;整列済み領域と先頭アドレスの位置の比較
JMI SOUNYU
CPA GR4,=’true’
JNZ SOUNYU
LD GR7,0,GR2 ;整列済みの比較している要素の中身をGR7に設定
CPA GR7,GR3 ;整列済みの比較位置の値と退避した値の比較
JMI FFF ;整列済みの方が小さかったらフラグをfalseへジャンプ
LAD GR2,1,GR2 ;整列済みの要素の1つ後ろにどける
ST GR7,0,GR2 ;値を1つ後ろにコピー
LAD GR2,-2,GR2 ;整列済みのアドレス値を戻してひとつ前へ
JUMP LOOP2
FFF LD GR4,=’false’
SOUNYU LAD GR2,1,GR2
ST GR3,0,GR2
LAD GR1,1,GR1
JUMP LOOP1
FIN OUT DATA,LEN
RPOP
RET
DATA DS 5
LEN DC 5
END
読んで下さってありがとうございました。
この記事を書くのに勉強になった本を紹介します。
多分この記事を読んで面白かったと思われた方は、
きっとハマると思います。
◆アルゴリズム問題がちゃんと解ける本
アルゴリズム学習の定番。
アルゴリズムが苦手で何とかしたい方におススメ
◆アルゴリズムはじめの一歩完全攻略
実際に作って学べます。
Javaを使っています。
私はJava初めてでしたが、
それでも、ハッシュ関数の所までは、
どうにかついていけました。
もっと頑張ります。
◆速習言語CASL2
CASL2、何それ、テーマパークの絶叫マシーン
みたいな名前だね、ぐらいだった私でも、入門書として楽しく読めた本です。
◆プログラミング入門CASL2
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。