データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム

Slides:



Advertisements
Similar presentations
7/10 if 文課題 力作が多くて感心! 演習1:キーボードから2つの整数を入力し、小さい方の数字を 表示せよ。
Advertisements

「コンピュータやネットワーク等の活用事例」
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
ヒープソートの演習 第13回.
アルゴリズムイントロダクション第2章 主にソートに関して
4.ソート 4-1.ソート問題について 4-2.簡単なソートアルゴリズム 4-3.高度なソートアルゴリズム
アルゴリズムとデータ構造 2012年6月27日
第12回 ソート(3): シェルソート、クイックソート
プログラミング 平成25年11月19日 森田 彦.
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
第11回 整列 ~ シェルソート,クイックソート ~
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
データ構造とアルゴリズム論 第5章 レコード構造を使った処理-クラスの利用
プロセッシング入門3 初歩のプログラミング.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015.
第10回 ソート(1):単純なソートアルゴリズム
アルゴリズムとデータ構造 補足資料7-3 「単純選択ソートselsort.c」
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
CGプログラミング論 平成28年4月27日 森田 彦.
ヒープソートの復習.
データ構造とアルゴリズム論 第2章 配列(構造)を使った処理
プログラミング 平成25年12月10日 森田 彦.
ネットワークプログラミング論 平成28年12月12日 森田 彦.
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
第11回 整列 ~ シェルソート,クイックソート ~
データ構造とアルゴリズム論 第9章 木構造 平成17年12月20日 森田 彦.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
データ構造とアルゴリズム論 第2回目テスト 平成15年12月9日 森田 彦.
データ構造とアルゴリズム論 第8章 再帰処理 平成15年12月2日 森田 彦.
データ構造と アルゴリズム論 平成29年9月27日 森田 彦.
CGプログラミング論 平成28年4月20日 森田 彦.
プログラミング 平成22年11月24日 森田 彦.
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
データ構造とアルゴリズム論 第3章 ファイルを用いたデータ入出力2
データ構造とアルゴリズム論 第3章 ファイルを用いたデータ入出力
わんくま同盟茶藝部顧問 Microsoft MVP for VC episthmh
データ構造とアルゴリズム論 第7章 再帰処理 平成17年12月6日 森田 彦.
データ構造とアルゴリズム論 第6章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第1章 アルゴリズムの表現-流れ図
ネットワークプログラミング論 平成28年12月19日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成29年12月20日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成30年6月27日 森田 彦.
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 整列アルゴリズム.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミングⅠ 平成31年1月7日 森田 彦.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとデータ構造 --- 理論編 --- 山本 真基
プログラミング 平成24年11月13日 森田 彦.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
アルゴリズムとプログラミング (Algorithms and Programming)
基本情報技術概論(第5回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
データ構造とアルゴリズム論 第7章 再帰処理 平成16年11月30日 森田 彦.
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
アルゴリズムとデータ構造 2012年6月25日
データ構造とアルゴリズム論 第9章 連結リスト
参考:大きい要素の処理.
プログラミング 平成24年12月11日 森田 彦.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム 平成30年5月30日 森田 彦

ソートとは? 幾つかのデータを、一定の基準(大きい順、小さい順等)に従って並べ替える操作 アルゴリズムの宝庫 アルゴリズム論学習の山場! 昇順 降順 (小さい順) (大きい順) アルゴリズムの宝庫 アルゴリズム論学習の山場!

本章(本日)の学習のねらい 基本的なソートアルゴリズムを学習し、その処理の流れを理解する。 → バブルソート、選択ソート、挿入ソート 基本的なソートアルゴリズムを学習し、その処理の流れを理解する。              → バブルソート、選択ソート、挿入ソート 3つのソートアルゴリズムの効率について考察する。 ソートアルゴリズムを実際のプログラムに応用する。

5-1 バブルソート 隣り合う2つのデータを比較し、「並べたい順になっていなければ入れ替える」という操作を繰り返す。  デモプログラム

<処理の流れ-4つのデータの昇順の場合> A 10 9 12 2 ソート開始 10 9 12 2 A[0]>A[1]なので交換する。 9 [2] [3] A 10 9 12 2 ソート開始 10 9 12 2 A[0]>A[1]なので交換する。 9 10 12 2 A[1]<A[2]なので交換しない。 9 10 12 2 A[2]>A[3]なので交換する。 9 10 2 12 A[3]の値確定。 9 10 2 12 A[0]<A[1]なので交換しない。 9 10 2 12 A[1]<A[2]なので交換する。 9 2 10 12 A[2]の値確定。 9 2 10 12 A[0]>A[1]なので交換する 2 9 10 12 A[0],A[1]の値確定。→完了!

アルゴリズムの整理 A[0]~A[n-1]のデータをソートする場合。 データの末尾から順番に値が確定して行く。 A[0],A[1],・・・,A[i],・・・,A[n-2],A[n-1] A[i]の値を確定するためには、A[0]~A[i]までの比較が必要。→i回の比較 A[i] {i=n-1,n-2,・・・,1}を確定するために  A[j]>A[j+1]の判定を{j=0~i-1}について行う。  2重のループが必要 → プリント p.81参照。 (右端) この流れ図の理解が本日のポイント!

5-2 選択ソート <考え方-昇順の場合> 選択ソート 10 9 6 2 ソート開始時 10 9 6 2 最小値(の位置)を見つける 10 5-2 選択ソート <考え方-昇順の場合> 選択ソート 10 9 6 2 ソート開始時 10 9 6 2 最小値(の位置)を見つける 10 9 6 2 1番目のデータと交換する 2 9 6 10 1番目データの値確定 2 9 6 10 最小値(の位置)を見つける 2 9 6 10 2番目のデータと交換する 2 6 9 10 2番目データの値確定 という操作を繰り返す。 流れ図→p.89参照

5-3 挿入ソート 部分的に整列されている場合に効果的 余分な比較をしなくて良い。 例:A[1]~A[3]が整列済み(昇順) A[4]を挿入 5-3 挿入ソート 部分的に整列されている場合に効果的 余分な比較をしなくて良い。 例:A[1]~A[3]が整列済み(昇順) 正しい位置に [1] [2] [3] [4] [5] A[4]を挿入 A 1 2 3 9 5 p.93の流れ図参照 1 2 3 9 5 A(3)<A(4)なので交換しない 1 2 3 9 5 A(1)~A(4)まで整列済み 1 2 3 9 5 A(5)を挿入 1 2 3 9 5 A(4)>A(5)なので交換する 1 2 3 5 9 A(3)<A(4)なので交換しない 1 2 3 5 9 ソート完了!

5-4 アルゴリズムの効率 比較回数と交換回数が少ないほど、効率は良い。 一般に・・・ 比較回数N: Nバブル=N選択≧N挿入 全てのペアについて比較 =n-1 プリント5-4節参照! バブルソートが最も効率が悪い。 一般には、挿入ソートが効率が良い場合が多い。

学習に当たって ソート(処理)はアルゴリズム論の山場となる重要なところです。 各ソートの処理の流れを、シミュレーションプログラムを利用してよく理解して下さい。 本日の学習のポイントは、各ソートの流れ図を理解できるかどうかです。→トレースして流れを確認できればOK 理解できない場合は「どの部分が理解できないのか?」を自分なりにしぼって森田に尋ねて下さい。 【応用課題5-A】まで終えた学生は、演習を終えて結構です。

順序の決まり方(整理) i n-1 j=0~n-2 n-2 j=0~n-3 i j=0~ ? i-1 j=0~1 2 j=0 1 ・・・ 位置が決定する要素 順序の決まり方(整理) A[0] A[1] ・・・ A[i] A[n-1] A[n-2] i n-1 j=0~n-2 A[j]とA[j+1]の比較(と交換) n-2 j=0~n-3 A[j]とA[j+1]の比較(と交換) ・・・ i A[j]とA[j+1]の比較(と交換) j=0~ ? i-1 ・・・ j=0~1 2 A[j]とA[j+1]の比較(と交換) j=0 1 A[j]とA[j+1]の比較(と交換)