アルゴリズムとデータ構造
第12週 データ整列：クイックソート法
2013年12月19日 金岡 晃
授業計画
第1週 (9/26)
データ構造とアルゴリズムの基 礎
第2週 (10/3)
アルゴリズムの効率、線形構造 第3週
(10/10)
スタックと待ち行列 第4週
(10/17)
文字列照合（KMP法、BM法）
第5週 (10/24)
木構造、木の走査
→文字列照合（BM法）、木構 造
第6週 (10/31)
木の走査、二分木、決定木
第8週 (11/21)
休講 第9週
(11/28)
グラフ構造と最短路問題 第10週
(12/5)
解の探索：Aアルゴリズム 第11週
(12/12)
データ整列：ヒープソート 法
第12週 (12/19)
データ整列：クイックソー ト法
第13週 (1/9)
データ探索：ハッシュ法 第14週 データ探索：木構造探索法
【復習】第 11 週
データ整列：ヒープソート法
アルゴリズムとデータ構造
2 2013/12/19 アルゴリズムとデータ構造
整列法の分類（１）
選択による方法
単純選択法、ヒープ整列法 選択：複数のデータの中から最大あるいは 最小のものを選ぶ動作
挿入による方法
単純挿入法（シャトル整列 法）、シェル法
挿入：すでに整列している複数のデータの 並びの適切な位置に、あらたな1枚を追加 挿入する操作
交換による方法
単純交換法（バブルソート 法）、クイックソート法
交換：注目した2枚の順番が逆になってい たら入れ替える動作
整列法の分類（２）
2013/12/19 アルゴリズムとデータ構造
4
併合による方法
併合整列法（マージソート 法）、多ウェイ併合法
併合：整列している2つのデータの並びを 統合して1つにする操作
分配による方法
バケット整列法 分配：データの先頭を見て、グループに大 まかに仕分ける操作
単純選択法
選択による方法
単純選択法、ヒープ整列法 選択：複数のデータの中から最大あるいは 最小のものを選ぶ動作
整列する対象の𝑛個のデータを𝑎 1 , ⋯ , 𝑎[𝑛]とする 単純選択法
入力データを全部調べて、最小のデータ𝑎 𝑝 の位置𝑝を知る。そして先頭𝑎 1 と𝑎 𝑝 を入れ替える。
この操作を、今度は先頭を除いた配列𝑎 2 , ⋯ , 𝑎[𝑛]に対して行う。
これを残りの配列が𝑎[𝑛]だけになるまで繰り返す
ヒープ整列法
2013/12/19 アルゴリズムとデータ構造
6
1次元配列データ𝑎 1 , ⋯ , 𝑎[𝑛]は、二分木の物理構造とみなすことができる。
𝑖
2𝑖 2𝑖 + 1
第𝑖要素𝑎 𝑖 の左の子と右の子を、それぞれ
𝑎 2𝑖 , 𝑎 2𝑖 + 1 と考えれば、1次元配列と二分木との
間を一意に対応づけることができる。
1次元配列を二分木と見なして整列する方法 ヒープ整列法（Heapsort）
ヒープ：親子関係にある任意の2つの節において、子節の値が親節の 値を超えないような準完全二分木
ヒープでは最大のデータは根に保持される特徴を利用する
ヒープ整列法のアルゴリズム
演習
2013/12/19 アルゴリズムとデータ構造
8
下記の1次元配列を二分木で表したデータをヒープ整列法で処理したときの、処 理の過程を図示せよ
30
40 80
10 60 55
1
2 3
4 5 6
第 12 週
データ整列：クイックソート法
アルゴリズムとデータ構造
本日の到達目標と概要
• 到達目標
– 系統的探索と、その実現方法としての A アルゴリズムの理解
• 概要
– 系統的探索
– 状態空間のモデル化 – 基本アルゴリズム
– ヒューリスティック関数 – A アルゴリズム
10 2013/12/19 アルゴリズムとデータ構造
整列法の分類（１）
選択による方法
単純選択法、ヒープ整列法 選択：複数のデータの中から最大あるいは 最小のものを選ぶ動作
挿入による方法
単純挿入法（シャトル整列 法）、シェル法
挿入：すでに整列している複数のデータの 並びの適切な位置に、あらたな1枚を追加 挿入する操作
交換による方法
単純交換法（バブルソート 法）、クイックソート法
交換：注目した2枚の順番が逆になってい たら入れ替える動作
クイックソート
2013/12/19 アルゴリズムとデータ構造
12
基準値となるキーを選択し、基準値より小さい数のデータ集合と基準値より 大きい数のデータ集合に分ける。
それぞれの集合についても、同じく基準値となるキーを選択し、2つのデー タ集合に分ける。
要素が1つ以下の集合となった場合、その集合は確定となる。
クイックソート法（Quick Sort）
クイックソートのアルゴリズム
straight-sort(x, y)は
単純な方法を使うことを 意味している
演習
2013/12/19 アルゴリズムとデータ構造
14
下記の1次元配列データをクイックソート法（前スライドのアルゴリズムを利 用）で処理したときの、処理の過程を記述せよ。このとき、 select(k)を、どう いう基準で選択したかを明確に記載すること。
ただし、過程の記述は各配列がどう変化していったかのみ記載すれば良いもの とする。また、ここではstraight-sort()を利用する閾値は10ではなく3とする。
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
30 40 80 35 60 70 55 10 20 50
