アウトライン
15-1 クイックソート
15-2 パソコン演習
15-3 課題
2
1. リストへの要素の挿入
2. インサーションソート
•要素の挿入によるソート
•「すでにソートされたリストへの要素の挿入」
を繰り返すことで，ソートを行う
3. クイックソート
•手順
•再帰プログラム
•分割統治法の考え方
4. 繰り返しでのステップ数
•ソートすべきデータサイズとステップ数の関係
今日の内容
3
15-1 クイックソート
4
８ １０ ６ ３ ５
リスト
pivot
１０
６ ３ ５
リストが空になるまで，pivot の選択と，
pivot による要素の分割を続ける
３ ５
pivot 以上
pivotより
小さい
pivot
pivot
分割 分割
クイックソートの考え方
5
1. 基準となるピボット（pivot）の選択
•ソートする範囲の中から pivot を1つ選ぶ
2. ピボットによるリストの分割
•smaller-items, larger-items を使用
3. 1 と2. を繰り返す
•2. で出来た「pivot より大きい要素のリスト」と「pivot
より小さい要素のリスト」のそれぞれを独立にソート
4. できた分割（木構造）を使ってソートを実行
•最後に、２つの部分と pivot をつなげる．全体がソート
できたことになる
•append を使用
クイックソートの処理手順
6
８ １０ ６ ３ ５
リスト
８
pivot
ソートする範囲の中から pivot を選ぶ
（ここでは，リストの先頭要素をpivot として
選んでいる）
pivot の選択
7
８１０ ６ ３ ５
リスト
８
pivot
分割されたリスト
１０
６ ３ ５
要素を1つずつ調べて、pivot より
小さい要素と，より大きい要素を分ける
pivot による要素の分割
8
リストが空になるまで，pivot の選択と，
pivot による要素の分割を続ける
８ １０ ６ ３ ５
リスト
pivot
１０
６３５
３ ５
pivot 以上
pivotより
小さい
pivot
pivot
分割 分割
9
15-2 パソコン演習
10
•資料を見ながら，「例題」を行ってみる
•各自，「課題」に挑戦する
•自分のペースで先に進んで構いません
パソコン演習の進め方
11
•DrScheme の起動
プログラム → PLT Scheme → DrScheme
•今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
12
•ソート済みのリストに，要素を挿入する関数 insert
を作り，実行する
•ここでは，要素が大きい順並んでいるものとする
•挿入を行うために，cons を使う
(80 21 10 7 5 4 3 1)
ソート済みのリスト
40
要素
(80 40 21 10 7 5 4 3 1)
例題１．要素の挿入
13
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題２に進んでください
(insert 40 (list 80 21 10 7 5 4))
「例題１．要素の挿入」の手順
14
関数 insert の定義
実行結果
実行結果の例
15
insert
(list 80 21 10 7 5 4)
40
(list 80 40 21 10 7 5 4)
入力 出力
入力は，ソート済みのリスト
と数値
出力はソート済みの
リスト
入力と出力
16
;; insert: number list-of-numbers->list-of-numbers
;; to create a list of numbers from n and the numbers
;; on alon that is sorted in descending order; alon is
;; already sorted
;; insert: number list-of-numbers(sorted)
;; -> list-of-numbers(sorted)
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])]))
17
1. リストが空ならば：→終了条件
(cons n empty) →自明な解
2. そうで無ければ：
–リストの先頭≦nならば
(cons n alon)
–リストの先頭＞nならば
「リストの rest にn を挿入し，その先頭
に，元のリストの先頭をつなげたもの」
が求める解
要素の挿入
18
(empty? alon)
(cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])
Yes
No
(cons nempty) が
自明の解である
19
•insert の内部に insert が登場
•insert の実行が繰り返される
例： (insert 40 (list 80 21 10 7 5 4))
= (cons 80 (insert 40 (list 21 10 7 5 4)))
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])]))
要素の挿入
20
(insert 40 (list 80 21 10 7 5 4)) から
(list 80 40 21 10 7 5 4)) が得られる過程の概略
(insert 40 (list 80 21 10 7 5 4))
= …
= (cons 80 (insert 40 (rest (list 80 21 10 7 5 4))))
= (cons 80 (insert 40 (list 21 10 7 5 4)))
= …
= (cons 80 (cons 40 (list 21 10 7 5 4)))
= (list 80 40 21 10 7 5 4)
21
(insert 40 (list 80 21 10 7 5 4)) から
(list 80 40 21 10 7 5 4)) が得られる過程の概略
(insert 40 (list 80 21 10 7 5 4))
= …
= (cons 80 (insert 40 (rest (list 80 21 10 7 5 4))))
= (cons 80 (insert 40 (list 21 10 7 5 4)))
= …
= (cons 80 (cons 40 (list 21 10 7 5 4)))
= (list 80 40 21 10 7 5 4)
これは，
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])]))
のalon を(list 80 21 10 7 5 4) で，nを40 で置き換えたもの 22
•例題１の insert を使って，リストをソートする関数 sort を
作り実行する
•ここでは，大きい順にソートする
(list 1 3 5 7 10 21 4 80)
(list 80 21 10 7 5 4 3 1)
例題２．インサーションソート
23
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
;; sort: list-of-numbers -> list-of-numbers
(define (sort alon)
(cond
[(empty? alon) empty]
[else (insert (first alon) (sort (rest alon)))]))
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題３に進んでください
(sort (list 3 5 1 4))
例題１
と同じ
「例題２．インサーションソート」の手順
24
実行結果
実行結果の例
25
sort
(list 3 5 1 4) (list 5 4 3 1)
入力 出力
入力はリスト 出力はソート済みの
リスト
入力と出力
26
;; sort: list-of-numbers -> list-of-numbers
(define (sort alon)
(cond
[(empty? alon) empty]
[else (insert (first alon) (sort (rest alon)))]))
;; insert: number list-of-numbers(sorted) -> list-of-numbers(sorted)
(define (insert n alon)
(cond
[(empty? alon) (cons nempty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon) (insert n(rest alon)))])])) 27
1. リストが空ならば：→終了条件
empty →自明な解
2. そうで無ければ：
「リストの rest をソートしたリスト
に対して，その先頭要素を挿入した
もの」が求める解
インサーションソート
28
(empty? alon)
(insert (first alon) (sort (rest alon)))
Yes
No
empty が自明の解である
29
•sort の内部に sort が登場
•sort の実行が繰り返される
例： (sort (list 3 5 1 4))
= (insert 3 (sort (list 5 1 4)))
(define (sort alon)
(cond
[(empty? alon) empty]
[else (insert (first alon) (sort (rest alon)))]))
インサーションソート
30
(sort (list 3 5 1 4)) から
(list 5 4 3 1)) が得られる過程の概略 (1/2)
(sort (list 3 5 1 4))
= …
= (insert 3 (sort (rest (list 3 5 1 4))))
= (insert 3 (sort (list 5 1 4)))
= …
= (insert 3 (insert 5 (sort (rest (list 5 1 4)))))
= (insert 3 (insert 5 (sort (list 1 4))))
= …
= (insert 3 (insert 5 (insert 1 (sort (rest (list 1 4))))))
= (insert 3 (insert 5 (insert 1 (sort (list 4)))))
= …
= (insert 3 (insert 5 (insert 1 (insert 4 (sort (rest (list 4)))))))
= (insert 3 (insert 5 (insert 1 (insert 4 (sort empty)))))
= …
= (insert 3 (insert 5 (insert 1 (insert 4 empty))))次ページへ 31
(sort (list 3 5 1 4)) から
(list 5 4 3 1)) が得られる過程の概略 (1/2)
(sort (list 3 5 1 4))
= …
= (insert 3 (sort (rest (list 3 5 1 4))))
= (insert 3 (sort (list 5 1 4)))
= …
= (insert 3 (insert 5 (sort (rest (list 5 1 4)))))
= (insert 3 (insert 5 (sort (list 1 4))))
= …
= (insert 3 (insert 5 (insert 1 (sort (rest (list 1 4))))))
= (insert 3 (insert 5 (insert 1 (sort (list 4)))))
= …
= (insert 3 (insert 5 (insert 1 (insert 4 (sort (rest (list 4)))))))
= (insert 3 (insert 5 (insert 1 (insert 4 (sort empty)))))
= …
= (insert 3 (insert 5 (insert 1 (insert 4 empty))))次ページへ
これは，
(define (sort alon)
(cond
[(empty? alon) empty]
[else (insert (first alon) (sort (rest alon)))]))
のalon を(list 3 5 1 4) で置き換えたもの
32
(sort (list 3 5 1 4)) から
(list 5 4 3 1)) が得られる過程の概略 (2/2)
= (insert 3 (insert 5 (insert 1 (insert 4 empty))))
= …
= (insert 3 (insert 5 (cons 4 (insert 1 (rest (list 4))))))
= (insert 3 (insert 5 (cons 4 (insert 1 empty))))
= …
= (insert 3 (insert 5 (cons 4 (cons 1 empty))))
= …
= (insert 3 (cons 5 (list 4 1)))
= …
= (cons 5 (insert 3 (list 4 1)))
= …
= (cons 5 (cons 4 (insert 3 (list 1)))
= …
= (cons 5 (cons 4 (cons 3 (list 1)))
= (list 5 4 3 1) 33
•リストを出力とするような関数
•要素の挿入
•インサーションソート
どれも cons を使用．
ここまでのまとめ
34
•インサーションソートについて，ステップ実
行を行い，繰り返し回数を数えてみる
•sort の実行回数はいくらか
•insert の実行回数はいくらか
例題３．インサーションソートでの繰り返し回数
35
•インサーションソートでの sort 関数の実行回数
リストの要素数を n とすると
n+1 回
例n=3 のとき）
(sort (list 80 30 50))
= (insert 80 (sort (list 30 50)))
= (insert 80 (insert 30 (sort (list 50))))
= (insert 80 (insert 30 (insert 50 (sort empty))))
36
•インサーションソートでの insert 関数の実行
回数
リストの要素数を n とすると
最小 n 回，最大 n(n+1)/2 回
例n=3 のとき）
sort □ □ □
→insert □sort □ □ 1,2,3回
→ insert □sort □1,2回
→ insert □sort 1回
insert では，内部で insert が再帰的に呼び出される
・１つめの insert では，0, 1, または 2回
・２つめの insert では，0, または 1回
・３つめの insert では，0 回
何回になるかは
データの並びで変わる
37
•インサーションソートでの insert 関数の実行回数
（平均）
リストの要素数を n とすると
1 + 1.5 + 2 + ・・・ + (n+1)/2 回= n2/4 + 3n/4
例n=3 のとき）
sort □ □ □
→insert □sort □ □ 1,2,3回
→ insert □sort □1,2回
→ insert □sort 1回
insert では，内部で insert が再帰的に呼び出される
・１つめの insert では，0, 1, または 2回 ：平均 1 回
・２つめの insert では，0, または 1回 ：平均 0.5 回
・３つめの insert では，0 回：平均 0 回38
•インサーションソートでの sort 関数の実行回数
リストの要素数を n とすると
n+1 回
例n=3 のとき）
(sort (list 80 30 50))
= (insert 80 (sort (list 30 50)))
= (insert 80 (insert 30 (sort (list 50))))
= (insert 80 (insert 30 (insert 50 (sort empty))))
39
n → ∞ では
n2/4 + 3n/4 → n2/4
•計算に要する時間は，n2に比例する
•3n/4 の項は無視できる
•n2/4 のうち「/4」の部分が意味があるのは
•insert の実行時間が，実際に何秒であるかが分か
る場合に限る
sort の実行回数（平均）
40
n n2/4 3n/4
1 0.25 0.75
2 1 1.5
5 6.25 3.75
10 25 7.5
100 2500 75
1000 250000 750
10000 25000000 7500
3n/4 の項は無視できる
41
•リストをつなげる関数 append を使ってみる
•append はScheme が備えている関数
例題４．append
42
1. 次の式を「実行用ウインドウ」で，実行しなさい
(append (list 1 2) (list 3 4))
(append (list 1 2) (list 3 4) (list 5 6))
(append (list 1 2) 3 (list 4 5))
☆次は，例題５に進んでください
「例題４．append」の手順
43
２つのリストを併合
３つのリストを併合
リストでないものは
併合できない 44
•数値のリスト alon と，数 threshold
を入力として，alon から threshold
以上の数を選んで，リストを出力す
る関数 larger-items を作り，実行す
る
•リストの要素を１つずつ調べる
例題５．大きな要素の選択
45
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題６に進んでください
(larger-items (list 1 2 3 10 11 12 4 5 6) 6)
「例題５．大きな要素の選択」の手順
46
実行結果
47
larger-iterms
(list 10 11 12 6)
入力 出力
alon の値：
(list 1 2 3 10 11 12 4 5 6)
threshold の値:
6
入力はリストと数値 出力はリスト
larger-iterms の入力と出力
48
;;larger-items: list-of-numbers number -> list-of-numbers
;; alon から threshold 以上の数を選びリストを作る
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])]))
49
1. リストが空ならば：→終了条件
empty →自明な解
2. そうで無ければ：
a. リストの first ≧threshold
「リストの rest に対する larger-items の
結果（リスト）の先頭に，リストの first
（数値）をつなげたもの」 が求める解
b. リストの first ＜threshold
「リストの rest に対する larger-items の
結果」 が求める解
大きな要素の選択
50
(empty? alon)
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])
Yes
No
empty が解
繰り返し処理
51
•larger-items の内部に larger-items が登場
•larger-items の実行が繰り返される
例： (larger-items (list 6 4 2) 3)
= (cons 6 (larger-items (list 4 2) 3))
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])]))
自明な解
終了
条件
繰り返し処理
52
(larger-items (list 6 2 4) 3) から
(list 6 4) が得られる過程の概略
(larger-items (list 6 2 4) 3)
= …
= (cons 6 (larger-items (list 2 4) 3))
= ...
= (cons 6 (larger-items (list 4) 3))
= ...
= (cons 6 (cons 4 (larger-items empty 3)))
= ...
= (cons 6 (cons 4 empty))
= (list 6 4) 53
(larger-items (list 6 2 4) 3) から
(list 6 4) が得られる過程の概略
(larger-items (list 6 2 4) 3)
= …
= (cons 6 (larger-items (list 2 4) 3))
= ...
= (cons 6 (larger-items (list 4) 3))
= ...
= (cons 6 (cons 4 (larger-items empty 3)))
= ...
= (cons 6 (cons 4 empty))
= (list 6 4)
これは，
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])]))
のalon を(list 6 2 4) で，threshold を3 で置き換えたもの 54
•数値のリスト alon と，数 threshold
を入力として，alon から threshold
より小さな数を選んで，リストを出
力するプログラム smaller-items を作
り，実行する
•リストの要素を１つずつ調べる
例題６．小さな要素の選択
55
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(< (first alon) threshold)
(cons (first alon)
(smaller-items (rest alon)threshold))]
[else (smaller-items (rest alon) threshold)])]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題７に進んでください
(smaller-items (list 1 2 3 10 11 12 4 5 6) 6)
「例題６．小さな要素の選択」の手順
56
実行結果の例
57
;; smaller-items: list-of-numbers number -> list-of-numbers
;; alon から threshold より小さな数を選びリストを作る
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(< (first alon) threshold)
(cons (first alon)
(smaller-items (rest alon)threshold))]
[else (smaller-items (rest alon) threshold)])])) 58
•数値のリスト alon をソートするための，ク
イックソートのプログラム quick-sort を作り，
実行する
•例題５の関数 larger-items と，例題６の関数
smaller-items を使う
•クイックソートの pivot（基準値）としては，リス
トの先頭要素を使う
•２つのリストと pivot をつなげて，全体として１
つのリストを作るために append を使う
例題７．クイックソート
59
1. 次を「定義用ウインドウ」で，実行し
なさい
•入力した後に，Execute ボタンを押す
(define (larger-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(>= (first alon) threshold)
(cons (first alon)
(larger-items (rest alon)threshold))]
[else (larger-items (rest alon) threshold)])]))
(define (smaller-items alon threshold)
(cond
[(empty? alon) empty]
[else
(cond
[(< (first alon) threshold)
(cons (first alon)
(smaller-items (rest alon)threshold))]
[else (smaller-items (rest alon) threshold)])]))
;; quick-sort : list-of-numbers -> list-of-numbers
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else
(append
(quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))]))
例題５
と同じ
例題４
と同じ
「例題７．クイックソート」の手順 (1/2)
60
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，課題に進んでください
(quick-sort (list 4 6 2))
(quick-sort (list 8 10 6 3 5))
「例題７．クイックソート」の手順 (2/2)
61
62
quick-sort
(list 2 4 6)
入力 出力
alon の値：
(list 4 6 2)
入力はリスト 出力はリスト
quick-sort の入力と出力
63
;; quick-sort : list-of-numbers -> list-of-numbers
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else
(append
(quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))]))
クイックソートのプログラム
64
８ １０ ６ ３ ５
リスト
pivot
１０
６ ３ ５
リストが空になるまで，pivot の選択と，
pivot による要素の分割を続ける
３ ５
pivot 以上
pivotより
小さい
pivot
pivot
分割 分割
クイックソートの考え方
65
•繰り返しの終了条件
•入力が空（empty）である
•入力は１つ
•ソートすべきリスト:alon
「クイックソートのプログラム」
の理解のポイント
66
1. empty ならば：→終了条件
empty →自明な解
2. そうで無ければ：
–リストの分割を行う
–結局，「リストが空になる」まで繰り返
す
クイックソートの繰り返し処理
67
•pivot による要素の分割で、smaller-items,
larger-items は，入力（リスト）よりも小さな
リストを生成する
•smaller-items, larger-items 内で呼び出される
quick-sort は，元の入力よりも小さなリストを
扱う
•最終的に，quick-sort は空リスト（empty）を
受け取る
クイックソートの終了条件
68
(empty? alon)
(append
(quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))
Yes
No
empty が解
繰り返し処理
69
•quick-sort の内部に quick-sort が登場
•quick-sort の実行が繰り返される
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else
(append
(quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))]))
自明な解
終了
条件
繰り返し処理
70
(quick-sort (list 6 2 4))
= …
= (append
(quick-sort (smaller-items (rest (list 6 2 4)) (first (list 6 2 4))))
(list (first (list 6 2 4)))
(quick-sort (larger-items (rest (list 6 2 4)) (first (list 6 2 4)))))]))
要するに、３つのリスト
(quick-sort (smaller-items (list 2 4) 6) → 6 以上
(list 6) → (list 6)
(quick-sort (larger-items (list 2 4) 6) → 6 未満
に分割されている
(quick-sort (list 6 2 4)) からの過程
71
•休暇旅行の旅程（家から旅先のホテルまで）
•家→空港
•空港→旅先の空港
•旅先の空港→ホテル
部分問題の例
72
1. 「基準値より大きい要素」のソート
2. 「基準値より小さい要素」のソート
クイックソートの部分問題
73
•サイズNの問題を解くのに、サイズが
約N/2の部分問題2つに分けて、それぞ
れを再帰的に解き、その後でその2つの
解を合わせて目的の解を得る
分割統治法 (divide and conquer)
74
•AddressNote 構造体のリストをソートするた
めの，クイックソートのプログラム quick-sort
を作り，実行する
•名前の順でソートする
•クイックソートの pivot（基準値）としては，リス
トの先頭要素を使う
•２つのリストと pivot をつなげて，全体として１
つのリストを作るために append を使う
例題８．クイックソート
75
;;larger-items: list of address-note, number -> listof numbers
;; a-list から threshold 以上の数を選びリストを作る
(define (larger-items a-list threshold)
(cond
[(empty? a-list) empty]
[else
(cond
[(string>=? (address-record-name (first a-list))
threshold)
(cons (first a-list)
(larger-items (rest a-list)threshold))]
[else (larger-items (rest a-list) threshold)])])) 76
;; smaller-items: list of data, number -> listof numbers
;; a-list から threshold より小さな数を選びリストを作る
(define (smaller-items a-list threshold)
(cond
[(empty? a-list) empty]
[else
(cond
[(string<? (address-record-name (first a-list))
threshold)
(cons (first a-list)
(smaller-items (rest a-list)threshold))]
[else (smaller-items (rest a-list) threshold)])])) 77
;; quick-sort : list of data -> list of numbers
(define (quick-sort a-list)
(cond
[(empty? a-list) empty]
[else
(append
(quick-sort (smaller-items (rest a-list)
(address-record-name (first a-list))))
(list (first a-list))
(quick-sort (larger-items (rest a-list)
(address-record-name (first a-
list)))))]))
クイックソートのプログラム
78
(quick-sort book) からの過程の概略
(quick-sort book)
= (quick-sort (list
(make-address-record "Mike" 10 "Fukuoka")
(make-address-record "Bill" 20 "Saga")
(make-address-record "Ken" 30 "Nagasaki")))
= ...
= (append
(quick-sort (smaller-items
(list
(make-address-record "Bill" 20 "Saga")
(make-address-record "Ken" 30 "Nagasaki"))
"Mike"))
(list (make-address-record "Mike" 10 "Fukuoka"))
(quick-sort (larger-items
(list
(make-address-record "Bill" 20 "Saga")
(make-address-record "Ken" 30 "Nagasaki"))
"Mike")) 79
15-3 課題
80
•関数 quick-sort （授業の例題５）についての問題
•(quick-sort (list 8 10 6 3 5)) から (list 3 5 6 8 10) が得ら
れる過程の概略を数行程度で説明しなさい
;; quick-sort : list-of-numbers -> list-of-numbers
(define (quick-sort alon)
(cond
[(empty? alon) empty]
[else
(append
(quick-sort (smaller-items (rest alon) (first alon)))
(list (first alon))
(quick-sort (larger-items (rest alon) (first alon))))]))
課題１
81
•次ページ以降にある「住所録構造体のクイック
ソート」についての問題
•(quick-sort book) の実行結果を報告しなさい
課題２．住所録構造体のクイックソート
82
(define-struct address-record
(name age address))
(define book (list
(make-address-record "Mike" 10 "Fukuoka")
(make-address-record "Bill" 20 "Saga")
(make-address-record "Ken" 30 "Nagasaki")))
(define (larger-items a-list threshold)
(cond
[(empty? a-list) empty]
[else
(cond
[(string>=? (address-record-name (first a-list)) threshold)
(cons (first a-list)
(larger-items (rest a-list)threshold))]
[else (larger-items (rest a-list) threshold)])]))
住所録構造体のクイックソート (1/2)
83
(define (smaller-items a-list threshold)
(cond
[(empty? a-list) empty]
[else
(cond
[(string<? (address-record-name (first a-list)) threshold)
(cons (first a-list)
(smaller-items (rest a-list)threshold))]
[else (smaller-items (rest a-list) threshold)])]))
(define (quick-sort a-list)
(cond
[(empty? a-list) empty]
[else
(append
(quick-sort (smaller-items (rest a-list)
(address-record-name (first a-list))))
(list (first a-list))
(quick-sort (larger-items (rest a-list)
(address-record-name (first a-list)))))]))
住所録構造体のクイックソート (2/2)
84
•リストからの検索プログラムの作成．
1. ある数 nが，数のリスト a-list に存在するかどう
かを検索する関数 search を作成し，実行結果を
報告しなさい
–存在するときに限り true を返す
2. ある数 nが，数のソート済みのリスト a-list に存
在するかどうかを検索するプログラム search-
sorted を作れ
–存在するときに限り true を返す
–search-sorted はリストがソート済みという事実を利用
しなくてはならない
課題３
85
