整列と配列処理のアルゴリズム

要点と定義

アルゴリズムは、入力から目的の結果を得るために、処理の順序や条件を定めた手順です。問題を解くときは、入力と出力、データの対応関係、繰返しの範囲、境界での動作を整理します。擬似言語や流れ図は、その手順を人が追える形で表す方法です。過年度の午後問題にはCOBOLやCASL IIなど旧言語を使ったものがありますが、そこに現れる整列、添字、カウンタ、ビット操作の考え方は基礎として有用です。旧試験形式や旧言語が現在も同じ形で出題されるという意味ではありません。

整列では、どの項目をキーにし、どの順に並べるかを比較規則として定めます。合計点の高い順なら合計点を降順キーにします。同点も含む順位を作る場合、処理した人数を表す通し番号と、表示する順位を別々に管理します。点数が変わったときだけ順位を通し番号に更新し、同点中は順位を変えません。たとえば点数が488、488、487の順なら、通し番号は1、2、3、順位は1、1、3です。順位は同点を共有するため、次の異なる値の順位が単純な連番とは限りません。

複数のキーで整列するときは、優先度の高いキーの順序を先に守ります。販売額を降順、同額なら最終販売日を昇順にする場合、隣接する2件を交換する条件は「左の販売額が小さい」または「販売額が等しく、左の日付が後」です。第二キーは第一キーが同じ場合だけ比較するので、日付の順序が販売額の順序を壊しません。

適用条件と例

配列や表を処理するときは、添字が何を指すかを区別します。販売データの行を走査する添字iと、会員番号を照合して得た会員管理側の行indexは別の意味です。たとえば販売データのi行目から販売額を読み、対応する会員のindex行に加算します。会員別の合計を配列で持つなら、行は会員、列は合計額などと役割を定め、添字と行・列の対応をそろえます。レコードを並べ替えるときは、番号・金額・日付など関連する項目を同じ単位で交換します。