アルゴリズムトップ
0. はじめに
1. アルゴリズム
1. アルゴリズムとは
2. 当ページの範囲
3. 良いアルゴリズム
4. フローチャートの書き方(記号)
5. フローチャートの書き方(構造)
6. 順次構造
7. 分岐構造
8. 反復構造
2. 順次構造
1. 代入
2. 計算
3. 入力
4. 出力
5. 練習問題1
6. 練習問題2
3. 分岐構造
1. 条件分岐
2. 単一分岐
3. 練習問題1
4. 多重分岐
5. 複合条件
6. ケース(多方向分岐)
7. 練習問題2
8. 練習問題3
4. 反復構造
1. 反復構造の種類
2. 前判定型
3. 後判定型
4. 練習問題1
5. 練習問題2
6. 練習問題3
7. 多重反復処理(ネスト)
8. 練習問題4
9. 練習問題5
5. 配列
1. 配列とは
2. 練習問題
3. ２次配列
4. 練習問題
5. 素数を求める,その1
6. 素数を求める,その2
6. 検索・ソート
1. サブルーチン
2. シーケンシャルサーチ
3. バイナリサーチ
4. 練習問題
5. ルックアップテーブル
6. ソートとは
7. 選択法
8. 交換法
9. バブルソート
10. 挿入法
11. クイックソート
12. 処理速度の比較
7. 文字列
1. 文字と文字列
2. 文字列処理
3. 文字列のコピー
4. 練習問題
5. 文字列の比較
6. 文字列の連結
7. 文字列の検索
| |
 前ページへ :
解答へ :
次ページへ
- 6-8.交換法
-
選択法では、要素数の２乗回比較するため効率が悪く、さらにソート前のAという
配列とソート後のBという配列が必要になるため不便である。
そこで選択法を少し発展させて、一番小さい値を消す（チェックする）のをやめ、
その選択された値と、それが入る順番の要素データを交換しながら処理することにする。
（下図参照）
こうすることにより、最小値を選び出す範囲が、「要素数、要素数-1、
要素数-2、・・・」と減っていくために、比較回数が半分となり処理速度が向上する。
さらに配列は１つで良いため、メモリー、手間の観点から言っても効率が良くなる。
|
|
|
|
|
|
| | 要素 | |
ソート前 | |
1回処理後 | |
2回処理後 | |
3回処理後 | |
4回処理後 | |
|
|
|
|
|
|
| 0 |
84 |
14 |
14 |
14 |
14 |
| 1 |
121 |
121 |
43 |
43 |
43 |
| 2 |
43 |
43 |
121 |
58 |
58 |
| 3 |
93 |
93 |
93 |
93 |
83 |
| 4 |
140 |
140 |
140 |
140 |
140 |
| 5 |
83 |
83 |
83 |
83 |
93 |
| 6 |
14 |
84 |
84 |
84 |
84 |
| 7 |
93 |
93 |
93 |
93 |
93 |
| 8 |
181 |
181 |
181 |
181 |
181 |
| 9 |
58 |
58 |
58 |
121 |
121 |
|
|
|
|
|
|
赤字：前回と値が変わったところ
青字：検索範囲の最小値
これを昇順にソートするアルゴリズムを考えてみてください。
ただし、メインルーチン、初期設定ルーチンは前ページの
ものをそのまま使い、表示ルーチンはB(i)を表示していたものをA(i)を表示するように
変更するだけでよい。
前ページへ :
解答へ :
次ページへ
|