sp-15.リスト処理とクイックソート

>100 Views

January 26, 22

スライド概要

(Scheme プログラミング)
URL: https://www.kkaneko.jp/cc/scheme/index.html

profile-image

金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

sp-15.リスト処理とクイック ソート (Scheme プログラミング) URL: https://www.kkaneko.jp/cc/scheme/index.html 金子邦彦 1

2.

アウトライン 15-1 クイックソート 15-2 パソコン演習 15-3 課題 2

3.

今日の内容 1. リストへの要素の挿入 2. インサーションソート • 要素の挿入によるソート • 「すでにソートされたリストへの要素の挿入」 を繰り返すことで,ソートを行う 3. クイックソート • • • 手順 再帰プログラム 分割統治法の考え方 4. 繰り返しでのステップ数 • ソートすべきデータサイズとステップ数の関係 3

4.

15-1 クイックソート 4

5.

クイックソートの考え方 10 pivot 以上 8 10 6 3 5 リスト pivot pivot 6 pivotより 小さい 分割 3 5 3 5 pivot 分割 リストが空になるまで,pivot の選択と, pivot による要素の分割を続ける 5

6.

クイックソートの処理手順 1. 基準となるピボット(pivot)の選択 • ソートする範囲の中から pivot を1つ選ぶ 2. ピボットによるリストの分割 • smaller-items, larger-items を使用 3. 1 と 2. を繰り返す • 2. で出来た「pivot より大きい要素のリスト」と「pivot より小さい要素のリスト」のそれぞれを独立にソート 4. できた分割(木構造)を使ってソートを実行 • • 最後に、2つの部分と pivot をつなげる.全体がソート できたことになる append を使用 6

7.

pivot の選択 8 10 6 3 5 リスト 8 pivot ソートする範囲の中から pivot を選ぶ (ここでは,リストの先頭要素を pivot として 選んでいる) 7

8.

pivot による要素の分割 10 8 10 6 3 8 5 リスト pivot 6 3 5 分割されたリスト 要素を1つずつ調べて、pivot より 小さい要素と,より大きい要素を分ける 8

9.

10 pivot 以上 8 10 6 3 5 リスト pivot pivot 6 3 5 pivotより 小さい 分割 3 5 pivot 分割 リストが空になるまで,pivot の選択と, pivot による要素の分割を続ける 9

10.

15-2 パソコン演習 10

11.

パソコン演習の進め方 • 資料を見ながら,「例題」を行ってみる • 各自,「課題」に挑戦する • 自分のペースで先に進んで構いません 11

12.

DrScheme の使用 • DrScheme の起動 プログラム • → PLT Scheme → DrScheme 今日の演習では「Intermediate Student」 に設定 Language → Choose Language → Intermediate Student → Execute ボタン 12

13.

例題1.要素の挿入 • ソート済みのリストに,要素を挿入する関数 insert を作り,実行する • ここでは,要素が大きい順並んでいるものとする • 挿入を行うために,cons を使う ソート済みのリスト (80 21 10 7 5 4 3 1) 要素 40 (80 40 21 10 7 5 4 3 1) 13

14.

「例題1.要素の挿入」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define (insert n alon) (cond [(empty? alon) (cons n empty)] [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)) ☆ 次は,例題2に進んでください 14

15.

実行結果の例 関数 insert の定義 実行結果 15

16.

入力と出力 (list 80 21 10 7 5 4) 40 (list 80 40 21 10 7 5 4) insert 入力 入力は,ソート済みのリスト と数値 出力 出力はソート済みの リスト 16

17.

;; 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 n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) 17

18.

要素の挿入 1. リストが空ならば: → 終了条件 (cons n empty) → 自明な解 2. そうで無ければ: – リストの先頭≦ n ならば (cons n alon) – リストの先頭>n ならば 「リストの rest に n を挿入し,その先頭 に,元のリストの先頭をつなげたもの」 が求める解 18

19.

(empty? alon) Yes No (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))]) (cons n empty) が 自明の解である 19

20.

要素の挿入 • insert の内部に insert が登場 (define (insert n alon) (cond [(empty? alon) (cons n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) • insert の実行が繰り返される 例: (insert 40 (list 80 21 10 7 5 4)) = (cons 80 (insert 40 (list 21 10 7 5 4))) 20

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) 21

22.

(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))) これは, =… (define (insert n alon) = (cons (cond 80 (cons 40 (list 21 10 7 5 4))) [(empty? (cons = (list 80 40alon) 21 10 7 n5empty)] 4) [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

23.

例題2.インサーションソート • 例題1の insert を使って,リストをソートする関数 sort を 作り実行する • ここでは,大きい順にソートする (list 1 3 5 7 10 21 4 80) (list 80 21 10 7 5 4 3 1) 23

24.

「例題2.インサーションソート」の手順 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 n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) 例題1 と同じ 2. その後,次を「実行用ウインドウ」で実行しなさい (sort (list 3 5 1 4)) ☆ 次は,例題3に進んでください 24

25.

実行結果の例 実行結果 25

26.

入力と出力 (list 3 5 1 4) (list 5 4 3 1) sort 入力 入力はリスト 出力 出力はソート済みの リスト 26

27.

;; 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 n empty)] [else (cond [(<= (first alon) n) (cons n alon)] [(> (first alon) n) (cons (first alon) (insert n (rest alon)))])])) 27

28.

インサーションソート 1. リストが空ならば: empty → 終了条件 → 自明な解 2. そうで無ければ: 「リストの rest をソートしたリスト に対して,その先頭要素を挿入した もの」が求める解 28

29.

(empty? alon) No Yes (insert (first alon) (sort (rest alon))) empty が自明の解である 29

30.

インサーションソート • sort の内部に sort が登場 (define (sort alon) (cond [(empty? alon) empty] [else (insert (first alon) (sort (rest alon)))])) • sort の実行が繰り返される 例: (sort (list 3 5 1 4)) = (insert 3 (sort (list 5 1 4))) 30

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)))) 次ページへ 31

32.

(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))))) (define (sort alon) = (insert 3 (insert 5 (sort (list 1 4)))) = … (cond [(empty? empty] = (insert 3 (insertalon) 5 (insert 1 (sort (rest (list 1 4)))))) = (insert 3 (insert 5 (insert 1 (sort (list (rest 4)))))alon)))])) [else (insert (first alon) (sort =… の alon を (list 3 5 1 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)))) 次ページへ 32

33.

(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

34.

ここまでのまとめ • リストを出力とするような関数 • 要素の挿入 • インサーションソート どれも cons を使用. 34

35.

例題3.インサーションソートでの繰り返し回数 • インサーションソートについて,ステップ実 行を行い,繰り返し回数を数えてみる • sort の実行回数はいくらか • insert の実行回数はいくらか 35

36.

• インサーションソートでの 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

37.

• インサーションソートでの insert 関数の実行 回数 リストの要素数を n とすると 最小 n 回,最大 n(n+1)/2 回 例 n=3 のとき) sort □ □ □ →insert □ sort □ □ → insert □ sort □ → insert □ sort 1,2,3回 1,2回 1回 insert では,内部で insert が再帰的に呼び出される ・1つめの insert では,0, 1, または 2回 何回になるかは ・2つめの insert では,0, または 1回 データの並びで変わる ・3つめの insert では,0 回 37

38.

• インサーションソートでの 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 が再帰的に呼び出される ・1つめの insert では,0, 1, または 2回 :平均 1 回 ・2つめの insert では,0, または 1回 :平均 0.5 回 ・3つめの insert では,0 回 :平均 0 回 38

39.

• インサーションソートでの 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

40.

sort の実行回数(平均) n→∞ では n2/4 + 3n/4 → n2/4 • 計算に要する時間は,n2 に比例する • 3n/4 の項は無視できる • n2/4 のうち「/4」の部分が意味があるのは • insert の実行時間が,実際に何秒であるかが分か る場合に限る 40

41.

3n/4 の項は無視できる 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 41

42.

例題4.append • リストをつなげる関数 append を使ってみる • append は Scheme が備えている関数 42

43.

「例題4.append」の手順 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)) ☆ 次は,例題5に進んでください 43

44.

2つのリストを併合 3つのリストを併合 リストでないものは 併合できない 44

45.

例題5.大きな要素の選択 • 数値のリスト alon と,数 threshold を入力として,alon から threshold 以上の数を選んで,リストを出力す る関数 larger-items を作り,実行す る • リストの要素を1つずつ調べる 45

46.

「例題5.大きな要素の選択」の手順 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) ☆ 次は,例題6に進んでください 46

47.

実行結果 47

48.

larger-iterms の入力と出力 alon の値: (list 1 2 3 10 11 12 4 5 6) threshold の値: 6 (list 10 11 12 6) larger-iterms 入力 入力はリストと数値 出力 出力はリスト 48

49.

;;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

50.

大きな要素の選択 1. リストが空ならば: empty → 終了条件 → 自明な解 2. そうで無ければ: a. リストの first ≧ threshold 「リストの rest に対する larger-items の 結果(リスト)の先頭に,リストの first (数値)をつなげたもの」 が求める解 b. リストの first < threshold 「リストの rest に対する larger-items の 結果」 が求める解 50

51.

繰り返し処理 (empty? alon) No Yes empty が解 (cond [(>= (first alon) threshold) (cons (first alon) (larger-items (rest alon) threshold))] [else (larger-items (rest alon) threshold)]) 51

52.

繰り返し処理 • larger-items の内部に larger-items が登場 (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)])])) • larger-items の実行が繰り返される 例: (larger-items (list 6 4 2) 3) = (cons 6 (larger-items (list 4 2) 3)) 52

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) 53

54.

(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 (listthreshold) 4) 3)) (define (larger-items alon = ... (cond [(empty? alon) empty] = (cons 6[else (cons 4 (larger-items empty 3))) (cond = ... [(>= (first alon) threshold) (cons (first alon) = (cons 6 (cons 4(larger-items empty)) (rest alon) threshold))] [else (larger-items (rest alon) threshold)])])) = (list 6 4) の alon を (list 6 2 4) で,threshold を 3 で置き換えたもの 54

55.

例題6.小さな要素の選択 • 数値のリスト alon と,数 threshold を入力として,alon から threshold より小さな数を選んで,リストを出 力するプログラム smaller-items を作 り,実行する • リストの要素を1つずつ調べる 55

56.

「例題6.小さな要素の選択」の手順 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) ☆ 次は,例題7に進んでください 56

57.

実行結果の例 57

58.

;; 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

59.

例題7.クイックソート • 数値のリスト alon をソートするための,ク イックソートのプログラム quick-sort を作り, 実行する • 例題5の関数 larger-items と,例題6の関数 smaller-items を使う • クイックソートの pivot(基準値)としては,リス トの先頭要素を使う • 2つのリストと pivot をつなげて,全体として1 つのリストを作るために append を使う 59

60.

「例題7.クイックソート」の手順 (1/2) 1. 次を「定義用ウインドウ」で,実行し なさい (define (larger-items alon threshold) • 入力した後に,Execute ボタンを押す (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))))])) 例題4 と同じ 例題5 と同じ 60

61.

「例題7.クイックソート」の手順 (2/2) 2. その後,次を「実行用ウインドウ」で実行しなさい (quick-sort (list 4 6 2)) (quick-sort (list 8 10 6 3 5)) ☆ 次は,課題に進んでください 61

63.

quick-sort の入力と出力 alon の値: (list 4 6 2) (list 2 4 6) quick-sort 入力 入力はリスト 出力 出力はリスト 63

64.

クイックソートのプログラム ;; 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

65.

クイックソートの考え方 10 pivot 以上 8 10 6 3 5 リスト pivot pivot 6 pivotより 小さい 分割 3 5 3 5 pivot 分割 リストが空になるまで,pivot の選択と, pivot による要素の分割を続ける 65

66.

「クイックソートのプログラム」 の理解のポイント • 繰り返しの終了条件 • 入力が空(empty)である • 入力は1つ • ソートすべきリスト: alon 66

67.

クイックソートの繰り返し処理 1. empty ならば: empty → 終了条件 → 自明な解 2. そうで無ければ: – リストの分割を行う – 結局,「リストが空になる」まで繰り返 す 67

68.

クイックソートの終了条件 • pivot による要素の分割で、smaller-items, larger-items は,入力(リスト)よりも小さな リストを生成する • smaller-items, larger-items 内で呼び出される quick-sort は,元の入力よりも小さなリストを 扱う • 最終的に,quick-sort は空リスト(empty)を 受け取る 68

69.

繰り返し処理 (empty? alon) No Yes empty が解 (append (quick-sort (smaller-items (rest alon) (first alon))) (list (first alon)) (quick-sort (larger-items (rest alon) (first alon)))) 69

70.

繰り返し処理 • 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))))])) • quick-sort の実行が繰り返される 70

71.

(quick-sort (list 6 2 4)) からの過程 (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)))))])) 要するに、3つのリスト (quick-sort (smaller-items (list 2 4) 6) (list 6) → (list 6) (quick-sort (larger-items (list 2 4) 6) に分割されている → 6 以上 → 6 未満 71

72.

部分問題の例 • 休暇旅行の旅程(家から旅先のホテルまで) • 家→空港 • 空港→旅先の空港 • 旅先の空港→ホテル 72

73.

クイックソートの部分問題 1. 「基準値より大きい要素」のソート 2. 「基準値より小さい要素」のソート 73

74.

分割統治法 (divide and conquer) • サイズNの問題を解くのに、サイズが 約N/2の部分問題2つに分けて、それぞ れを再帰的に解き、その後でその2つの 解を合わせて目的の解を得る 74

75.

例題8.クイックソート • AddressNote 構造体のリストをソートするた めの,クイックソートのプログラム quick-sort を作り,実行する • 名前の順でソートする • クイックソートの pivot(基準値)としては,リス トの先頭要素を使う • 2つのリストと pivot をつなげて,全体として1 つのリストを作るために append を使う 75

76.

;;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

77.

;; 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

78.

クイックソートのプログラム ;; 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

79.

(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

80.

15-3 課題 80

81.

課題1 • 関数 quick-sort (授業の例題5)についての問題 • (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

82.

課題2.住所録構造体のクイックソート • 次ページ以降にある「住所録構造体のクイック ソート」についての問題 • (quick-sort book) の実行結果を報告しなさい 82

83.

住所録構造体のクイックソート (1/2) (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)])])) 83

84.

住所録構造体のクイックソート (2/2) (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)))))]))84

85.

課題3 • リストからの検索プログラムの作成. 1. ある数 n が,数のリスト a-list に存在するかどう かを検索する関数 search を作成し,実行結果を 報告しなさい – 存在するときに限り true を返す 2. ある数 n が,数のソート済みのリスト a-list に存 在するかどうかを検索するプログラム searchsorted を作れ – – 存在するときに限り true を返す search-sorted はリストがソート済みという事実を利用 しなくてはならない 85