ヒューマン・リソース・マシーン 入社41年目−並べ替えよ

目次

１）課題

０を終端とした文字列がいくつか流れてきます。各文字列に対してソート（並べ替え）を行い、小さい順（昇順）に右側へ運んでください。

２）状況の確認

この問題では, 予めコードが入っています. このコードを実行して, 何をするコードなのか確かめます. 

左のコンベアからパネルを取り出し, カーペットに配置しています. 終端を表す０を配置したところで終了しています. また, 使用したカーペットの最大値がカーペットの20番に記録してあります. 

３）考え方

カーペットに配置したパネルを小さい順に並べ替える方法を考えます. ここでは, 終端を表す０に近いカーペットから順に大きい数字のパネルを置くように考えていきます. アドレスの判定を簡単にするためです. 

ここで, 入社23年目の「一番小さいのは？」を振り返ります. この課題では, 一番小さいパネルを選びました. この課題を応用します. 

上の図では, カーペットの3番が０となっています. カーペットの2番に, 最大の数字を配置する方法を考えます. 

1. カーペットの2番をチャンピオンとします.
2. カーペットの1番をチャンピオンに挑ませます. 1番の方が大きければ, チャンピオンを交代します.
3. 同じようにしてカーペットの0番をチャンピオンに挑ませ, 大きければ交代します.

最大の数字が決まれば, カーペットの2番をチャンピオンとして同様に処理します. この操作を繰り返すことで, パネルを並び替えられます.

４）カーペットの名前

カーペットには, 並べ替えるパネル以外にも, 管理用のカーペットが必要です. 

次のように名前を付けました.

1. アドレス：処理中のカーペットを表します. チャンピオンを決定する時は, チャレンジャーの位置を表します.
2. チャンピオン：チャンピオンのいるカーペットの位置を表します.
3. SWAP：チャレンジャーが勝った場合, チャンピオンとチャレンジャーを入れ替えるために使います. 
4. ZERO：初期化用の０を置いておきます.

５）全体的な枠組み

カーペットの位置を示す「アドレス」と「チャンピオン」を書き換える処理を中心にコードを書いていきます.

8行目の時点で, 「アドレス」には終端を表す「0」を配置したカーペットの番号が入っています. 8行目から10行目で「チャンピオン」に反映します. 

11行目で, 「チャンピオン」が０になっているか判定しています. 「チャンピオン」が０なら, 並び替えが終わっているので, 運び出すだけです. 

12行目から「チャンピオン」の値を使って「アドレス」の値を「チャンピオン」の値－1としています. ここでの「アドレス」は「チャレンジャー」の意味です. 「アドレス（チャレンジャー）」がマイナスなら, 「チャンピオン」の防衛が決まったので, 10行目に戻り, 次の「チャンピオン」を決めます. 

15行目で「アドレス（チャレンジャー）」を取り出し, 「チャンピオン」に挑ませます. 

結果がマイナス, つまりチャンピオンの方が大きければ13行目に戻り, 次のチャレンジャーに挑ませます. 

結果がプラス, つまりチャレンジャーの方が大きければ, チャレンジャーとチャンピオンを入れ替えます. ここでは, 「SWAP」と書いたラベルを配置してあるだけで, コードの中身はこれから書きます.

「アドレス（チャレンジャー）」が「チャンピオン」より大きい場合, 「SWAP」を使って「アドレス（チャレンジャー）」を「チャンピオン」を入れ替えます. 入れ替え後に「アドレス（チャレンジャー）」を1減らし, 次のチャレンジャーに挑ませます.

11行目で「チャンピオン」がマイナスかを判定しています. マイナスの場合, すべてのパネルの順序が決まり, ソートが完了しました. パネルを小さい方から順に右のコンベアに運びます. 最初に左のコンベアから取り出したパネルをカーペットに配置しましたが, その逆のことをしています. 

クリアーできました. サイズ目標は3行も少なく達成できました. スピード目標を達成するには,もう少し工夫が必要です.

目次