この記事では、アセンブラ言語で「挿入法」について簡単な例題で学べます。
シンプルな図解を用いています。また、アセンブラの本の紹介もしています。
挿入法について、別名「ぶち込み法」と命名しました(=^x^=)
＜＜関連記事＞＞
基本情報技術者試験トップへ
アセンブラ自作サンプルへ
アセンブラ過去問プログラムへ
令和2年（令和3年1月）合格報告
2020年からの基本情報技術者試験は、言語とアルゴリズムの配点が高くなりました。
なので、プログラミング未経験の事務員の私は、非常に焦っていましたが、無事合格できました。
学習中のアウトプットを少し編集してお届けしております。
疑似言語によるアルゴリズムをCASL2で再現してみたら、両方学べて
一石二鳥なのではと思い、今回は「挿入法」を作ってみました。
気づいたことですが、
挿入法って「ぶち込み法」だと思うと、
分かりやすいのかもしれないです。
挿入法は、既に整列済みの範囲の中に、
今見ている値を適切な位置に順々にぶち込んで行きます。
配列DATAに、「CBEAD」と入力します。
これを「ABCDE」に揃えます。
CASL2では文字コードで大小を判断して、
例えばAなら41、Bなら42…と比較して探します。
この例で行くと、
既に整列済みのCに対して、
今GR1で見ているBをぶち込みます。
この時、GR2で指す範囲は、
配列の先頭の要素0から、GR1より1つ前までです。
GR1が右に進んでいくほど、GR2の動ける範囲が
多くなります。
Bを作業領域（TEMP）のGR3に
退避します。
その後、ループのフラグを「true」にします。
フラグはGR4で示します。
配列DATAの先頭アドレス（固定）をGR5に設定します。
配列DATAの末尾のアドレス（固定）をGR6に設定します。
GR2が指す値をGR7に設定します。
CとBで、Cの方が大きいなので、
Cを1つ右にどかすイメージでコピーします。
GR2を1つ前に移動させます。
GR2が配列の先頭より前になったので、
ループを抜けます。
GR3に退避したBを、
Cがあった所にぶち込むイメージでコピーします。
最初のループ修了では、こうなりました。
これで、要素0にB、要素1にCが来て整列済みになりました。
次はEを要素2のEをぶち込む処理をします。
GR1は要素2のEを指し、GR2は、要素1～要素0の
範囲で動きます。
EはGR3に退避させます。
フラグはtrueです。
CはEより小さいので、
GR4のフラグを「False」にしてループを抜けます。
次は要素3のAを処理します。
GR3にAを退避させます。
ループのフラグをtrueにします。
要素3のAを整列済みのBCDの適切な位置にぶち込んでいきます。
EとAを比べて、Eの方が大きいので、Eを1つ後ろにどかすイメージで
コピーします。
GR2を1つ前に移動させます。
次に、AとCでは、Cの方が大きいので、Cを1後ろに
どかすイメージでコピーします。
GR2を1つ前に移動させます。
次に、AとBでは、Bの方が大きいので、Bを1後ろに
どかすイメージでコピーします。
GR2を1つ前に移動させます。
GR2が配列の先頭より前になったので、ループを抜けます。
GR3に退避したAを要素0にぶち込みます。
最後にDをぶち込む処理をします。
GR3にDを退避させます。
EとDではEの方が大きいので、
Eを右にどかすイメージでコピーします。
GR2を1つ前にします。
次に、CとDを比較します。
Cの方が小さいので、フラグをFalseにして、
ループを抜けます。
Dをぶち込むイメージでコピーします。
これで整列が完了しました。
出力結果になります。
プログラミングです。
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
入門が卒業出来たら、ガシガシ例題解いて、
演習問題を解いて、力を付けたいという時に
読む本です。