第 １ ８ 章 問 題 サ イ ズ の 縮 小 に 基 づ く ソ ー テ ィ ン グ
１ ． 問 題 サ イ ズ の 縮 小
あ る 大 き い 問 題 を 解 く と き 、 そ の 問 題 を 簡 単 化 し て 、 よ り 小 さ な 問 題 に 置 き 換 え て 解 決 を 図 る こ と が ET プ ロ グ ラ ミ ン グ の 基 本 的 な 考 え 方 で あ る 。 数 を 対 象 と し た 問 題 で は 、 与 え ら れ た 数 よ り も 小 さ い 数 の 問 題 に 簡 単 化 す る こ と が 多 く 、リ ス ト を 対 象 と し た 問 題 で は 、 与 え ら れ た リ ス ト の 長 さ を 短 く し て 、 問 題 を 簡 単 化 す る こ と が 多 い 。
簡 単 化 に 基 づ く 問 題 解 決 法 を ソ ー テ ィ ン グ に 適 用 し て 考 え て み よ う 。 ソ ー テ ィ ン グ の 場 合 、 数 リ ス ト の 要 素 を 減 ら し て い く 方 法 と し て 、 次 の ３ つ が 考 え ら れ る 。
① 数 リ ス ト を 、 先 頭 の 要 素 と 残 り の 要 素 の リ ス ト に 分 け る
② 数 リ ス ト を 、 最 小 値 と そ の 残 り の 要 素 の リ ス ト に 分 け る
③ 数 リ ス ト の 中 か ら 基 準 と な る 数 を 決 め 、 そ の 数 よ り も 小 さ い 数 か ら な る リ ス ト と 、 そ れ よ り も 小 さ く な い 数 か ら な る リ ス ト に 分 け る
数 リ ス ト を 縮 小 す る こ れ ら の ３ つ の 方 法 に 対 応 し て 、 ３ つ の ソ ー テ ィ ン グ 法 が 導 か れ る 。
① → イ ン サ ー ト ・ ソ ー ト ② → 選 択 ソ ー ト
③ → ク イ ッ ク ソ ー ト
２ ． 問 題 サ イ ズ を 縮 小 す る プ ロ グ ラ ム
① の 縮 小 方 法 は 、(*A|*X) と *X と い う パ タ ー ン の 組 で 簡 単 に 実 現 で き る 。 以 下 で は 、
② と ③ に あ た る 縮 小 方 法 を 実 現 す る プ ロ グ ラ ム を 作 る 。
２ ． １ 数 リ ス ト を 、 最 小 値 と そ の 残 り の 要 素 の リ ス ト に 分 け る (1) 最 初 の 要 素 と 残 り の リ ス ト へ 分 割 す る
例 え ば 、(3 9 1 7) が 与 え ら れ た と き 、 最 小 値 は １ で 、 残 り の 要 素 の リ ス ト は 、(3 9 7) な ど が あ る（ 残 り の リ ス ト の 要 素 の 順 番 は 任 意 な の で 、正 解 は 何 と お り か あ る ）。最 小 値 の 位 置 は 任 意 で あ る の で 、(1 3 9 7)で も(3 1 9 7)で も 問 題 に 対 す る 答 え は 変 わ ら な い 。 こ の よ う な プ ロ グ ラ ム を つ く る と き 、 ま ず 、 与 え ら れ た リ ス ト を 、
最 初 の 要 素 と 残 り の リ ス ト へ 分 割 す る
と い う 方 法 を 考 え て み よ う 。「 最 小 値 と 残 り 」 の 意 味 で 、 述 語 名 を minrest と す る 。 す る
と 、minrest は 次 の ２ つ の 問 題 を 考 え る こ と に な る 。
(minrest (*A|*X) *M *Y) … リ ス ト(*A|*X) の 最 小 値 が*M で 残 り の リ ス ト が*Y (minrest *X *N *Z) … リ ス ト*X の 最 小 値 が*N で 残 り の リ ス ト が*Z
ま ず 、(minrest (*A|*X) *M *Y)を 別 の 簡 単 な 条 件 に 置 き 換 え る こ と を 目 的 に 、(minrest (*A|*X) *M *Y) の 中 の *M や *Y が ど う い う 条 件 を 満 た す か を 考 え て み よ う 。 こ こ で は 、
*M や*Y を ど の よ う に 求 め る か を 示 す ア ル ゴ リ ズ ム を 一 度 に す べ て 与 え る 必 要 は な い 。 我 々 は
(minrest *X *N *Z) … リ ス ト*X の 最 小 値 が*N で 残 り の リ ス ト が*Z
を 仮 定 し て い る の で 、*N や*Z は 既 知 と し 、そ れ ら を 使 う こ と で*M や*Yが ど う 決 ま る か を 考 え れ ば よ い 。
ま ず *M に つ い て 考 え て み よ う 。*M は(*A|*X)の 中 の 全 て の 要 素 の 最 小 値 で あ る 。*X に お け る 要 素 の 個 数 は わ か ら な い の で ､*M を(*A|*X)か ら 求 め る の は 難 し い 。し か し 、リ ス ト
*X の 最 小 値 が*N で あ る こ と が わ か っ て い る 。こ れ は*X の 部 分 に 対 す る 重 要 な 情 報 で あ る 。
*N を 使 え ば 、(*A|*X)の 最 小 値*M を 求 め る こ と に 一 歩 近 づ き 、*N と *Aを 比 較 す る こ と で 達 成 さ れ る 。 す な わ ち 、
*N よ り *A が 小 さ い と き 、 *Mは*A に 等 し い *N よ り *A が 大 き い と き 、 *Mは*N に 等 し い
*N と *A が 等 し い と き 、 *Mは*N と も*A と も 等 し い
こ と が わ か る 。３ 行 目 の*N と *Aが 等 し い 場 合 は 、１ 行 目 か ２ 行 目 の ど ち ら か に 包 括 で き る 。 そ こ で 、 次 の ２ つ の 場 合 を 考 え る 。
*N よ り *A が 大 き く な い と き 、 *Mは*A に 等 し い *N よ り *A が 大 き い と き 、 *Mは*N に 等 し い
ち な み に 、本 節 で は 、大 小 関 係 を「 大 き い 」「 小 さ い 」で 記 述 す る と 等 号 の 扱 い が 不 明 瞭 に な る の で 、「 大 き い 」 と 「 大 き く な い 」 に 分 け て 記 述 し て い る 。 こ う し て 、 最 小 値*M が わ か る 。 残 り の リ ス ト に つ い て は 、 以 下 の こ と が わ か る 。
*N よ り *A が 大 き く な い と き 、 残 り の リ ス ト は*X に な る
*N よ り *A が 大 き い と き 、 最 小 値 が*N だ か ら 、 残 り は*Z と*Aで あ る
以 上 よ り 、 問 題 を 簡 単 化 す る ル ー ル が 書 く こ と が で き る 。
例 題 ）
次 の ア ト ム を 使 っ て 、 上 述 の 簡 単 化 ル ー ル を 書 き な さ い 。
(minrest (*A|*X) *M *Y) … リ ス ト(*A|*X) の 最 小 値 が*M で 残 り の リ ス ト が*Y (minrest *X *N *Z) … リ ス ト*X の 最 小 値 が*N で 残 り の リ ス ト が*Z
こ の ル ー ル を 作 る と き 、 ま ず ヘ ッ ド を
(minrest (*A|*X) *M *Y)
と 書 き 、 ボ デ ィ の 先 頭 に
(minrest *X *N *Z)
を 書 く 。最 小 値 や 残 り の リ ス ト を 求 め る に は 、*N と*A を 比 較 し な け れ ば な ら な い 。そ れ に は*N と*Aが 両 方 と も 求 ま っ て い な け れ ば な ら な い 。 し た が っ て 、*N と*Aの 比 較 は 、 こ の ル ー ル の 最 初 で は で き ず 、(minrest *X *N *Z) を 処 理 し た 後 に 行 う 必 要 が あ る 。 そ の 処 理 は い く つ か の 組 み 込 み ア ト ム で は 実 現 で き な い の で 、新 し い ア ト ム を 導 入 す る 必 要 が あ る 。 そ こ で 、aux 述 語 を 導 入 す る 。
(aux *A *N *Z *M *Y)
こ の 形 の ア ト ム を 処 理 し て 、*Aと*N と*Z か ら 、最 小 値*M と 残 り の リ ス ト*Y を 求 め よ う と い う の で あ る 。 こ う し て 、
(minrest (*A|*X) *M *Y) --> (minrest *X *N *Z), (aux *A *N *Z *M *Y).
と い う １ つ の ル ー ル を 得 た と す る 。 こ の ル ー ル を 具 体 的 な 問 題 に 適 用 し て み よ う 。 例 え ば 、
（minrest (4 2 1 3) *M *Y）
を 質 問 と し て 与 え る と 、 ル ー ル が 何 回 か 適 用 さ れ た 後 、 実 行 は 失 敗 す る 。 残 さ れ た ア ト ム 列 の 先 頭 に は 、
(minrest () *m *y)
の 形 の ア ト ム が 出 現 す る 。 こ れ は 、 現 在 の ル ー ル が 適 用 で き な い ア ト ム で あ る 。 実 際 、 現 在 の ル ー ル は 第 １ 引 数 が 空 リ ス ト の と き は 適 用 で き な い 。 そ こ で 、 こ の ア ト ム を 正 し く 簡 単 化 す る ル ー ル を 導 入 す る 必 要 が あ る 。
(minrest () *m *y) は 何 に 簡 単 化 す れ ば よ い だ ろ う か 、 空 リ ス ト の と き の 答 え は ど う な る だ ろ う か を 考 え た な ら ば 、 空 リ ス ト の と き は 、 最 小 値 は な い と 気 づ く こ と が で き る だ ろ う 。
最 初 に ル ー ル を 書 く と き 、
(minrest *X *N *Z) … リ ス ト*X の 最 小 値 が*N で 残 り の リ ス ト が*Z
が 成 功 し て 、 最 小 値 や 残 り の リ ス ト が 決 ま る と 仮 定 し た 。 た だ し 、*X が 1 つ 以 上 要 素 を 含 む と い う 条 件 が 必 要 で あ る 。 そ れ を 満 た さ な い と き に は 、 最 小 値 や 残 り の リ ス ト は な い の で ル ー ル を 適 用 し て は な ら な か っ た の で あ る 。 こ の ル ー ル は 適 用 条 件 が 広 す ぎ る と い う 誤 っ た ル ー ル で あ っ た 。 そ こ で 、
最 初 の 要 素 と 残 り の リ ス ト へ 分 割 す る
と い う 考 え を 改 め て 、
最 初 の 要 素 と 2 番 目 の 要 素 と 残 り の リ ス ト へ 分 割 す る
と い う 別 の 考 え で 試 み よ う 。
例 題 ）
次 の ア ト ム を 使 っ て 、 上 述 の 簡 単 化 ル ー ル を 書 き 直 し な さ い 。
(minrest (*A *B|*X) *M *Y) … (*A *B|*X) の 最 小 値 が*M で 残 り が*Y (minrest (*B|*X) *N *Z) … (*B|*X) の 最 小 値 が*N で 残 り が*Z
こ の よ う に 、 リ ス ト の 長 さ が ２ 以 上 の と き に 適 用 で き る ル ー ル を 記 述 す る こ と で 、 空 リ ス ト に な る ま で 問 題 が 簡 単 化 さ れ る と い う 誤 り を 防 ぐ こ と が で き る 。
(minrest (*A *B|*X) *M *Y) --> (minrest (*B|*X) *N *Z), (aux *A *N *Z *M *Y).
こ の 新 し い ル ー ル を 改 め て 具 体 的 な 問 題 に 適 用 し て み よ う 。 例 え ば 、
（minrest (4 2 1 3) *M *Y）
を 質 問 と し て 与 え る と 、 実 行 は や は り 失 敗 す る が 、 残 さ れ た ア ト ム 列 の 先 頭 に は 、
(minrest (3) *m *y)
の 形 の ア ト ム が 出 現 す る は ず で あ る 。 今 度 は こ の ア ト ム に 答 え が あ る 。 最 小 値 は 3で 、 残 り の リ ス ト は( )で あ る 。こ の 答 を 知 る た め の 一 般 的 な ル ー ル は 何 で あ ろ う か 。リ ス ト の 最
後 の 要 素 は 任 意 の 数 で あ る の で 、
(minrest (*A) *m *y)
の 形 の ア ト ム を 簡 単 化 す る 一 般 的 な ル ー ル が 必 要 で あ る 。
以 上 よ り 、 リ ス ト の 長 さ が 「 ２ 以 上 」 の 場 合 と 、「 １ 」 の 場 合 の 2 つ の ル ー ル を 、 再 び 質 問 に 適 用 し よ う 。 今 度 も 実 行 は 失 敗 す る が 、 計 算 は 着 実 に 進 ん で お り 、minrest の ア ト ム は 、こ の ２ つ の ル ー ル の 適 用 に よ っ て 消 滅 し た 。残 さ れ た ア ト ム 列 の 先 頭 に は 、aux ア ト ム が く る で あ ろ う 。 し た が っ て 、aux ア ト ム を 処 理 す る ル ー ル を 書 け ば よ い 。
(aux *A *N *Z *M *Y), {(<= *A *N)} --> (= *M *A), (= *Y (*N|*Z)).
(aux *A *N *Z *M *Y) --> (= *M *N),(= *Y (*A|*Z)).
こ の よ う に し て 、minrestア ト ム を 解 決 す る ル ー ル 集 合 が 得 ら れ る 。 (2) 前 か ら 少 し ず つ 処 理 す る
前 節 で は 、 与 え ら れ た リ ス ト を 、 最 初 の 要 素 と 残 り の リ ス ト へ 分 割 す る こ と か ら 出 発 し て プ ロ グ ラ ム を 導 い た 。 こ れ は 1 つ の 典 型 的 な 問 題 の 簡 単 化 の 方 法 で あ る 。 し か し 、 得 ら れ た ル ー ル は 末 尾 再 帰 で は な い 。 主 要 な ル ー ル は 、
minrest → minrest, aux
と い う 形 で あ り ､ボ デ ィ の 先 頭 で 再 帰 的 な 処 理 を や る と い う 重 い 形 で あ る 。
そ こ で 、 別 の 簡 単 化 を 試 み る こ と に し よ う 。 リ ス ト の 先 頭 の 部 分 だ け を 見 て 、 も し 答 え の 一 部 で も わ か れ ば 、そ れ を 積 み 上 げ て 答 え を 作 り 出 す こ と が 期 待 で き る 。そ の よ う な「 軽 い 」 ア プ ロ ー チ を 試 み る 。 再 び 質 問 の 例 を 見 て み よ う 。 例 え ば 、(3 9 1 7) が 与 え ら れ た と き 、 最 小 値 は １ で 、 残 り の 要 素 の リ ス ト は 、 例 え ば(3 9 7)で あ る 。 残 り の リ ス ト の 要 素 の 順 番 は 任 意 な の で 、(3 9 7)の 順 序 を 入 れ 替 え た す べ て の リ ス ト が 答 で あ る 。 要 は 3 と 7 と 9が 最 小 値 以 外 の 数 で あ る と い う こ と で あ る 。(3 9 1 7)の 前 の 部 分 だ け を 見 て 、 答 え の 一 部 分 で も 知 る こ と が で き る だ ろ う か 。(3 9 1 7)の 最 も 前 の 部 分 と は 3で あ る 。 こ れ は 残 り の リ ス ト(3 9 7)の 先 頭 に あ る 。し か し こ れ を 一 般 化 し て 、(*A|*X)の 最 小 値 以 外 の リ ス ト の 先 頭 は*A に な る と は い え な い 。 た と え ば 、(1 9 3 7) が 与 え ら れ た と き 、 最 小 値 は 1 で 、 残 り の リ ス ト は(3 9 7)で あ る 。1 は(3 9 7)の 先 頭 に は な ら な い 。
(3 9 1 7)を 見 て 、 残 り の リ ス ト に 9が 入 る と 断 定 す る た め に は 、 リ ス ト の 2 番 目 の 要 素 ま で を 見 る 必 要 が あ る 。先 頭 に は 9よ り 小 さ い 3が あ る の で 、9は 最 小 値 に は な り 得 な い 。 し た が っ て 、9 は 残 り の リ ス ト に 入 れ て も よ い こ と が わ か る 。 こ の よ う に 、 リ ス ト の 2 番 目 の 要 素 ま で 見 て 、 そ れ ら を 比 較 す れ ば 、 残 り の リ ス ト の 要 素 と し て 入 れ て よ い 数 が １ つ は わ か る 。
(5 3 | *R) の と き 、 残 り の リ ス ト に 5が 入 る は ず で あ る (1 7 | *R) の と き 、 残 り の リ ス ト に 7が 入 る は ず で あ る (4 4 | *R) の と き 、 残 り の リ ス ト に 4が 入 る は ず で あ る
こ れ か ら ル ー ル が 書 く こ と が で き る で あ ろ う 。そ れ を 質 問 (3 5 2 4)に 適 用 す れ ば 、リ ス ト の 長 さ が １ で あ る(2)の 問 題 が 未 解 決 の 問 題 と し て 得 ら れ る 。こ の よ う な 長 さ 1の リ ス ト の 問 題 は 簡 単 に 解 く こ と が で き 、 ル ー ル は す ぐ に 思 い つ く で あ ろ う 。
２ ． ２ リ ス ト を 数 の 比 較 を 用 い て ２ つ の リ ス ト に 分 割 す る
数 と 数 リ ス ト が 与 え ら れ 、 そ の リ ス ト を 、 そ の 数 未 満 の 要 素 か ら な る リ ス ト と 、 そ の 数 以 上 の 要 素 か ら な る リ ス ト に 分 け る 問 題 を 考 え る 。こ の 問 題 を 、「 前 か ら 少 し ず つ 処 理 す る ル ー ル 」 を 作 る 方 針 で 解 決 し よ う 。
３ ． 結 果 と し て 得 ら れ る ソ ー テ ィ ン グ の 方 法 ３ ． １ イ ン サ ー ト ソ ー ト
5 ?
( 5 | 2 1 3 4) S (1 2 3 4 5) (2 1 3 4) ⇒ (1 2 3 4) ?
S
リ ス ト を 最 初 の 要 素 と 残 り の リ ス ト に 分 け る 。 こ の 最 も 単 純 な 分 け 方 か ら ど の よ う な ア ル ゴ リ ズ ム が 出 て く る か を 考 え よ う 。
例 え ば 、(5 2 1 3 4)と い う よ う な リ ス ト を ソ ー テ ィ ン グ す る 場 合 、 最 初 の 要 素 と 残 り の リ ス ト に 分 け る と 、(2 1 3 4)と い う 小 さ な 問 題 が で き る 。こ れ を ソ ー テ ィ ン グ し た 答 え は 、 (1 2 3 4)で あ る 。 一 方 、 全 体 を ソ ー テ ィ ン グ し た 場 合(1 2 3 4 5)と い う 答 え を 得 た い 。 こ の 最 終 的 な 答 え は 、 小 さ な 問 題 の 答 え で あ る(1 2 3 4)か ら ど の よ う に し て 作 ら れ る の か 。 そ れ に は 当 然 5も 使 う わ け で あ る 。 (1 2 3 4)が 既 に あ り 、 そ れ か ら(1 2 3 4 5)を 作 る た め に は 、5 を (1 2 3 4)の 適 切 な 場 所 に 入 れ る 。 こ の 場 合 は リ ス ト の 末 尾 で あ る 。 こ う し て 全 体 の ソ ー テ ィ ン グ が で き る 。 こ の ソ ー テ ィ ン グ を イ ン サ ー ト ソ ー ト と 呼 ぶ 。 こ こ で は ２ つ の ア ト ム を 使 う 。
(isort (*A|*X) *Y) … (*A|*X) を ソ ー ト す る と*Y に な る (isort *X *Z) … *X を ソ ー ト す る と*Zに な る
こ の ２ つ を 用 い る と 、 残 さ れ た 仕 事 は 、*A と*Z か ら*Yを 作 る こ と で あ る 。
(insert *A *Z *Y) … *A を*Zに 入 れ て 整 列 さ れ た*Y を 作 る
②先頭の要素を挿入する
①先頭を除いた残りの要素 をソーティングする
②先頭の要素を挿入する
①先頭を除いた残りの要素 をソーティングする
例 題 ）
あ る 要 素 を 昇 順 の リ ス ト に 挿 入 し て 、 昇 順 の リ ス ト を つ く る プ ロ グ ラ ム を 記 述 し な さ い 。(insert 5 (2 4 8 10) (2 4 5 8 10))
insert の ル ー ル は 、
(insert *A *Z *Y) … *A を*Zに 入 れ て 整 列 さ れ た*Y を 作 る
と い う ア ト ム か ら 出 発 し よ う 。*Z は 既 に ソ ー ト さ れ て い る こ と に 注 意 し な さ い 。 あ と は 、
*A が 入 る 位 置 を 決 め れ ば*Y が 得 ら れ る 。*A と*Zの 先 頭 要 素 を 見 れ ば 、*Yが あ る 程 度 予 想 で き る 。
① *A=5, *Z=(1 2 6 7) の と き 、5 ＞1 な の で 、*Y の 先 頭 は 1 で 、 残 り は (insert 5 (2 6 7) *W)
に よ っ て 決 ま る*W で あ る 。
② *A=1, *Z=(2 5 6 7) の と き 、1 ＜ 2 な の で 、*Y の 先 頭 は 1 で 、 残 り は*Z で あ る ③ *A=2, *Z=(2 5 6 7) の と き 、2 = 2な の で 、*Yの 先 頭 は 2で 、 残 り は*Z で あ る
こ れ か ら 容 易 に insertの ル ー ル を 作 る こ と が で き よ う 。
３ ． ２ 選 択 ソ ー ト
S
1 ?
(5 2 1 3 4) S (1 2 3 4 5) (5 2 3 4) ⇒ (2 3 4 5) ?
リ ス ト を 最 小 値 と そ の 残 り の 要 素 の リ ス ト に 分 け る 場 合 を 考 え て み よ う 。
あ る リ ス ト(5 2 1 3 4） が 与 え ら れ た と き 、 こ の 中 で 最 も 小 さ な 数 で あ る １ と 、 そ れ 以 外 の 要 素 の リ ス ト に 分 け る 。そ う し て 得 ら れ る の が (5 2 3 4)で あ る 。こ こ で 得 ら れ た 小 さ な 問 題 の 解 答 は 、(2 3 4 5)で あ る 。 こ の 解 答 が 得 ら れ た と き 、 全 体 の 問 題 の 解 答 は 、(1 2 3 4 5)と な る 。
(2 3 4 5)か ら 、(1 2 3 4 5)を 作 り 出 す の は 極 め て 簡 単 で あ る 。1番 最 初 に 取 り 出 し た １ を (2 3 4 5)の 先 頭 に つ け れ ば よ い 。 こ う し て 、 全 体 の 答 え(1 2 3 4 5) が 得 ら れ る 。
３ ． ３ ク イ ッ ク ソ ー ト
S
(2 1) ⇒ (1 2) ?
( 3 2 1 5 4) 3 (1 2 3 4 5) S
(5 4) ⇒ (4 5) ?
S
?
リ ス ト の 中 か ら 基 準 と な る 数 を 決 め 、 そ の 数 よ り も 小 さ い 数 か ら な る リ ス ト と 、 そ れ よ り も 大 き い 数 か ら な る リ ス ト に 分 け る 場 合 を 考 え よ う 。
例 え ば 、(3 2 1 5 4)と い う リ ス ト が 与 え ら れ た 場 合 、 リ ス ト の 先 頭 要 素 （ こ の 場 合 は 3）
を 用 い て 、 全 体 を 「 そ れ よ り も 小 さ い も の 」 と 「 そ れ よ り も 大 き い も の 」 に 分 割 す る 。 こ の 場 合 、3 よ り 小 さ い も の は(2 1)で あ り 、 大 き い も の は(5 4)で あ る 。 し た が っ て 、 (2 1) と (5 4)と い う 小 さ い 問 題 が ２ つ で き る 。そ れ を ソ ー テ ィ ン グ し た 結 果 は 、そ れ ぞ れ(1 2)、
(4 5)と な る 。 こ の よ う に ソ ー テ ィ ン グ さ れ た 結 果 と 3を あ わ せ て 、 最 終 的 に(1 2 3 4 5)を 得 る た め に は ど う す れ ば よ い か を 考 え る 。
(1 2)は 求 め る リ ス ト の 先 頭 の 位 置 に あ た り 、(4 5)は 末 尾 の 位 置 に あ た り 、そ し て 3 は 両 者 の 間 の 位 置 に あ た る 。 し た が っ て 、 そ れ ぞ れ を(1 2)、3、(4 5)の 順 序 で つ な ぐ と 答 え が 得 ら れ る 。
基準
sort1 sort2
基準よりも小 基準よりも大 基準
基準
sort1 sort2
基準よりも小 基準よりも大
sort１ と sort２ は 再 帰 的 に 同 じ 計 算 を 行 う 。
基準
sort1
sort2
基準よりも小 基準よりも大 基準
基準
sort1
sort2
基準よりも小 基準よりも大
こ の ソ ー テ ィ ン グ は 、 リ ス ト の 分 割 を 実 行 す る 述 語 divide(2.2 節 参 照)の 他 に 、 分 割 さ れ た リ ス ト を 結 合 す る 述 語 append が 必 要 に な る 。
divide と append の ル ー ル が 、 リ ス ト を 分 割 し 結 合 す る と い う 、 ク イ ッ ク ソ ー ト の 下 請 け 部 分 を 実 行 す る の で 、 あ と は 、 そ れ ら を 用 い て 全 体 の 処 理 を 記 述 す れ ば 、 ク イ ッ ク ソ ー ト が 行 わ れ る 。
