第 １ ７ 章 ソ ー テ ィ ン グ
１ ． ソ ー テ ィ ン グ と は
ソ ー テ ィ ン グと は 、 対 象 の デ ー タ を 指 定 し た 順 序 で 並 べ 替 え る こ と で あ る 。 実 際 の ケ ー ス で 考 え て み る と 、 伝 票 を 日 付 順 で 並 べ 替 え た り 、 名 簿 を 五 十 音 順 に 並 べ た り し て 、 デ ー タ を 整 理 す る 機 会 が よ く あ る 。 充 分 に カ ッ ト さ れ た ト ラ ン プ を 小 さ い 順 に 並 べ 替 え る こ と も ソ ー テ ィ ン グ で あ る 。
ET プ ロ グ ラ ミ ン グ で は 、 デ ー タ が 数 の 場 合 、 デ ー タ の 列 を 数 リ ス ト で 表 現 し 、 そ れ を 小 さ い 順（ 昇 順 ）ま た は 大 き い 順（ 降 順 ）に 並 べ 替 え る 。 例 え ば 、 上 記 の ト ラ ン プ の ソ ー テ ィ ン グ を 数 リ ス ト で 表 現 す る と 、 以 下 の よ う に な る 。
(3 2 4 1 5) → (1 2 3 4 5)
数 リ ス ト を 昇 順 や 降 順 に ソ ー テ ィ ン グ す る 他 の 例 を 以 下 に 示 す 。 ま た 、 リ ス ト の 中 に 重 複 し た 数 が あ っ て も 、 ソ ー ト は 成 功 す る 。
(4 7 8 1 2 9) , 昇 順 → (1 2 4 7 8 9) (3 7 2 3 8) , 昇 順 → (2 3 3 7 8) (3 2 4 5 1) , 降 順 → (5 4 3 2 1) (4 2 7 7 6) , 降 順 → (7 7 6 4 2)
91
２ ． 逆 転 数
数 リ ス ト が 与 え ら れ た と き 、 そ れ が 「 ソ ー ト さ れ て い な い 度 合 い 」 は 、 逆 転 数 で 測 る こ と が で き る 。 数 リ ス ト の 逆 転 数 と は 、 数 リ ス ト の 要 素 の 任 意 の ペ ア の う ち 、 昇 順 で な い ペ ア の 総 数 の こ と で あ る 。 例 え ば 、(3 1 2)と い う リ ス ト の 場 合 、 ペ ア は 3－1、1－2、3
－2 の 3 組 考 え ら れ る 。こ の う ち 3－1と 3－2だ け が 逆 転 し て い る の で 、逆 転 数 は 2 と な る 。
数 リ ス ト の 逆 転 数 が ０ で あ る と い う こ と は 、 そ の 数 リ ス ト が そ の ま ま で ソ ー ト さ れ た 状 態 に な っ て い る と い う こ と で あ る 。 逆 転 数 が 1 以 上 で あ れ ば 、 数 リ ス ト の 中 に 大 小 関 係 が 逆 転 し て い る ペ ア が 少 な く と も 1組 は あ る は ず で あ る 。そ の よ う な 逆 転 の ペ ア を 入 れ 替 え た と き 、 逆 転 数 は 必 ず 1 減 少 す る 。
３ ． バ ブ ル ソ ー ト
隣 り 合 う 逆 転 の ペ ア の 入 れ 替 え を 続 け る と 、 逆 転 数 は 減 少 を 続 け る 。 し か し 逆 転 数 は 負 に は な ら な い の で 、 永 久 に 逆 転 ペ ア の 入 れ 替 え を 行 う こ と は で き な い 。 逆 転 数 が ０ に な る ま で 入 れ 替 え を 行 う と 、 与 え ら れ た 数 リ ス ト は 必 ず 入 れ 替 え で き な い 状 態 、 す な わ ち 、 正 し く 整 列 さ れ た 状 態 に な る 。 こ の よ う な ソ ー テ ィ ン グ の 方 法 をバ ブ ル ソ ー トと 呼 ぶ ｡ バ ブ ル ソ ー ト で は 、 逆 転 の ペ ア の 交 換 を 1 回 行 う と 、 交 換 さ れ る 要 素 は 整 列 さ れ た 状 態 へ 1つ 移 動 す る 。要 素 は 1 回 に つ き 1つ し か 移 動 し な い 。小 さ い 要 素 が 1つ ず つ 前 方 に 移 動 す る 様 子 が 、 軽 い 泡 が 重 い 水 と 入 れ 替 わ っ て 浮 か び 上 が っ て い く 動 き に 似 て い る の で バ ブ ル ソ ー ト と 呼 ば れ て い る 。
例 え ば 、(3 4 1 2)と い う リ ス ト を 考 え 、 バ ブ ル ソ ー ト に し た が っ て 昇 順 に ソ ー テ ィ ン グ し て み よ う 。 ま ず 、 リ ス ト の ３ と ４ の ペ ア は 昇 順 で あ る の で 、 要 素 の 入 れ 替 え を 行 う 必 要 は な い 。 次 に ４ と １ の ペ ア を 検 証 す る 。 こ の ペ ア は 昇 順 で は な く 、 交 換 を 実 行 す る 必 要 が あ る 。 す る と
(3 1 4 2)と い う リ ス ト に な る 。 そ し て 、3 と 1 の ペ ア は 交 換 が 必 要 な の で 、 交 換 を 実 行 す る 。 す る と 、(1 3 4 2)と い う リ ス ト に な る 。 こ の よ う に し て 、 さ ら に 2回 逆 転 ペ ア の 交 換 を 行 う と 、(1 2 3 4) が 得 ら れ る 。 こ れ で ソ ー テ ィ ン グ が 完 了 す る 。
92
隣 り 合 う 2つ の 数 を 比 較 し て 、 逆 転 と ペ ア の 交 換 を 行 う
４ ． 隣 り 合 う 逆 転 ペ ア の 発 見
バ ブ ル ソ ー ト を 実 現 す る た め に は 、 隣 り 合 う 逆 転 ペ ア を 発 見 し 、 そ の ペ ア を 交 換 し た 新 し い リ ス ト に 置 き 換 え る よ う な プ ロ グ ラ ム を 作 る 必 要 が あ る 。 そ の よ う な 逆 転 ペ ア が あ る か な い か に よ っ て 、 プ ロ グ ラ ム の 動 き を 変 え る 必 要 が あ る 。 そ の 2 つ を 区 別 す る た め に 、 プ ロ グ ラ ム の 実 行 の 「 成 功 と 失 敗 」 を 利 用 す る こ と が で き る 。
リ ス ト の 先 頭 の 要 素 と 2 番 目 の 要 素 を 比 べ る 。 そ れ が 逆 転 ペ ア で な い と き に は 、 １ つ 小 さ い 問 題 に 簡 単 化 す る 。 そ れ が 逆 転 ペ ア の 場 合 で あ れ ば 、 す ぐ に 答 え が 求 ま る 。 リ ス ト の 要 素 が 1個 以 下 の 場 合 は 、 比 較 す る ２ つ の 要 素 が リ ス ト 中 に 存 在 し な い の で 、 逆 転 ペ ア は な い 。
５ ． バ ブ ル ソ ー ト の プ ロ グ ラ ム
バ ブ ル ソ ー ト は 、 リ ス ト 中 に 交 換 す べ き 逆 転 ペ ア が あ る か ど う か を 判 定 し 、 そ の よ う な ペ ア が あ れ ば 交 換 し 、ま た 最 初 か ら 逆 転 ペ ア を 探 索 す る 。リ ス ト の 末 尾 ま で 探 索 し た 結 果 、 そ の よ う な ペ ア が 見 つ か ら な け れ ば 、 そ の リ ス ト を 答 と す れ ば よ い 。
例 え ば 、
(bsort (10 12 6 8 4) *Z)
と い う 問 題 を 考 え る 。 バ ブ ル ソ ー ト に よ れ ば 、 以 下 の よ う に リ ス ト の 要 素 の 交 換 が 行 わ れ て い く 。
93
(10 12 6 8 4) → (10 6 12 8 4) (10 6 12 8 4) → (6 10 12 8 4) (6 10 12 8 4) → (6 10 8 12 4) (6 10 8 12 4) → (6 8 10 12 4) (6 8 10 12 4) → (6 8 10 4 12) (6 8 10 4 12) → (6 8 4 10 12) (6 8 4 10 12) → (6 4 8 10 12) (6 4 8 10 12) → (4 6 8 10 12)
結 果 と し て 、(4 6 8 10 12) が 得 ら れ る 、 こ れ に は 交 換 す べ き ペ ア が な い (exchange ル ー ル が 失 敗 す る )の で 、 こ の リ ス ト が 問 題 の 答 と な る 。
６ ． 逆 転 数 の 減 少 の 様 子 を 表 示 す る
例 え ば 「 リ ス ト==> ×× ， 逆 転 数==> ○ ○ 」 と い う 文 を 表 示 さ せ た い と き 、 第 11 章 で 取 り あ げ た formatと い う 組 み 込 み 述 語 を 用 い て 、 以 下 の よ う に 記 述 す れ ば よ い 。
(format "リ ス ト==> /a ， 逆 転 数==> /a /n" (*A *B))
94
