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

Slides:



Advertisements
Similar presentations
プログラミング 平成24年1月11日 森田 彦.
Advertisements

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

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

基礎課題提出状況(11/11) 平均提出数=25.6 (全課題数28) 約7割が25題以上を提出

応用課題提出状況(11/11) 平均提出課題数=8.0 13題以上提出は約22%

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

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

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

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

アルゴリズムの特徴 A[1]~A[n]のデータをソートする場合。 データの末尾から順番に値が確定して行く。A[n]→A[n-1],・・・,A[i],・・・,A[2] A[i]の値を確定するためには、A[1]~A[i]までの比較が必要。→(i-1)回の比較 A[i] {i=n,n-1,・・・,2}を確定するために  A[j]>A[j+1]の判定を{j=1~i-1}について行う。  2重のループが必要 → プリント p.89参照。 ※ A[0]~A[n-1]としている。

6-2 選択ソート <考え方-昇順の場合> 10 9 6 2 ソート開始時 10 9 6 2 最小値(の位置)を見つける 10 9 6 2 6-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.97参照

6-3 挿入ソート 部分的に整列されている場合に効果的 余分な比較をしなくて良い。 例:A[1]~A[3]が整列済み(昇順) A[4]を挿入 6-3 挿入ソート 部分的に整列されている場合に効果的 余分な比較をしなくて良い。 例:A[1]~A[3]が整列済み(昇順) [1] [2] [3] [4] [5] A[4]を挿入 A 1 2 3 9 5 p.101の流れ図参照 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 ソート完了!

6-4 アルゴリズムの効率 比較回数と交換回数が少ないほど、効率は良い。 一般に・・・ 比較回数N: Nバブル=N選択≧N挿入 全てのペアについて比較 選択ソート (=n-1) 整列済みデータの場合は、逆転する場合あり バブルソートが最も効率が悪い。 挿入ソートが効率が良い場合が多い。

Windows updateについて 2003年11月12日(日本時間)、マイクロソフト社より深刻度が緊急とされるセキュリティ上の修正プログラムが公開。 修正プログラム が適用されていないシステムは、侵入やワームによる感染などの被害を受ける可能性があります。 各自速やかに、Windows updateを実行して下さい。