12,905
回編集
「C++の基礎 - ソート」の版間の差分
ナビゲーションに移動
検索に移動
→単純選択法 (選択ソート)
(ページの作成:「== 概要 == <br><br> == 単純選択法 (選択ソート) == 単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。<br> <br> # まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。 # 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。 #…」) |
|||
| 17行目: | 17行目: | ||
単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。<br> | 単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。<br> | ||
配列の長さをnとすると、計算量は <math>O(n^2)</math> となる。<br> | 配列の長さをnとすると、計算量は <math>O(n^2)</math> となる。<br> | ||
<br> | |||
また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。<br> | また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。<br> | ||
ただし、必要な追加のメモリ容量が少ないというメリットがある。<br> | ただし、必要な追加のメモリ容量が少ないというメリットがある。<br> | ||
| 84行目: | 85行目: | ||
ソート後の配列: 11 12 22 25 34 50 64 90 | ソート後の配列: 11 12 22 25 34 50 64 90 | ||
<br><br> | |||
== 単純挿入法 (挿入ソート) == | |||
単純挿入法 (挿入ソート) は、トランプのカードを手に持って整理する時の動作に似たソートアルゴリズムである。<br> | |||
<br> | |||
配列を<u>"ソート済み部分"</u>と<u>"未ソート部分"</u>に分けて、未ソート部分から要素を1つずつ取り出し、ソート済み部分の適切な位置に挿入する。<br> | |||
<br> | |||
# まず、配列の先頭要素をソート済みと看做して、2番目の要素から順に処理する。 | |||
# 処理対象の要素 (key) を一時的に保持して、ソート済み部分を後ろから順に走査して、keyより大きい要素は1つ右にずらす。 | |||
# そして、最終的にkeyよりも小さい要素を見つけた位置 (または配列の先頭) の右側にkeyを挿入する。 | |||
<br> | |||
単純挿入法 (挿入ソート) の特徴として、既にある程度ソートされているデータに対しては効率的に動作する。<br> | |||
これは、ソート済み部分での探索が早く終わるからである。<br> | |||
また、同じ値の要素の相対的な順序が保たれるため、安定なソートである。<br> | |||
<br> | |||
計算量においては、最悪の場合で <math>O(n^2)</math> となるが、ほぼソートされているデータに対しては <math>O(n)</math> に近い性能を示す。<br> | |||
<br> | |||
メモリ使用量は、ソートを配列内で直接行うことができるため、追加のメモリをほぼ必要としないというメリットがある。<br> | |||
<br> | |||
<syntaxhighlight lang="c++"> | |||
#include <iostream> | |||
using namespace std; | |||
int main() | |||
{ | |||
int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50}; | |||
int n = 8; // 配列のサイズ | |||
cout << "ソート前の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
// 挿入ソートのアルゴリズム | |||
for (int i = 1; i < n; i++) { | |||
int key = arr[i]; // 挿入する値 | |||
int j = i - 1; // ソート済み部分の末尾 | |||
// keyより大きい要素を右にずらす | |||
while (j >= 0 && arr[j] > key) { | |||
arr[j + 1] = arr[j]; | |||
j = j - 1; | |||
} | |||
arr[j + 1] = key; | |||
// 各ステップでの配列の状態を表示 | |||
cout << "ステップ " << i << ": "; | |||
for (int k = 0; k < n; k++) { | |||
cout << arr[k] << " "; | |||
} | |||
cout << endl; | |||
} | |||
cout << "ソート後の配列: "; | |||
for (int i = 0; i < n; i++) { | |||
cout << arr[i] << " "; | |||
} | |||
cout << endl; | |||
return 0; | |||
} | |||
</syntaxhighlight> | |||
<br><br> | <br><br> | ||