C++の基礎 - ソート
概要
単純選択法 (選択ソート)
単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。
- まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。
- 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。
- この操作を、配列の最後の要素の手前まで繰り返すことにより、データを昇順 (または降順) に整列することができる。
例えば、{5, 3, 1, 4, 2}という配列をソートする場合、
まず最初の位置から開始して、全体から最小値 (この場合では1) を見つけて、最初の位置 (この場合では5) と交換する。
次に、2番目の位置 (この場合では3) から開始して残りの要素から次の最小値の2を見つけて、3と交換する。
この処理を順々に繰り返す。
単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。
配列の長さをnとすると、計算量は となる。
また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。
ただし、必要な追加のメモリ容量が少ないというメリットがある。
#include <iostream>
using namespace std;
int main()
{
// 配列 (要素数8) を初期化
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 = 0; i < n - 1; i++) {
// 未ソート部分から最小値を探す
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 最小値を見つけたら、現在の位置と交換
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
// 各ステップでの配列の状態を表示
cout << "ステップ " << i+1 << ": ";
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;
}
# 出力例: ソート前の配列: 64 34 25 12 22 11 90 50 ステップ 1: 11 34 25 12 22 64 90 50 ステップ 2: 11 12 25 34 22 64 90 50 ステップ 3: 11 12 22 34 25 64 90 50 ステップ 4: 11 12 22 25 34 64 90 50 ステップ 5: 11 12 22 25 34 64 90 50 ステップ 6: 11 12 22 25 34 50 90 64 ステップ 7: 11 12 22 25 34 50 64 90 ソート後の配列: 11 12 22 25 34 50 64 90
単純挿入法 (挿入ソート)
単純挿入法 (挿入ソート) は、トランプのカードを手に持って整理する時の動作に似たソートアルゴリズムである。
配列を"ソート済み部分"と"未ソート部分"に分けて、未ソート部分から要素を1つずつ取り出し、ソート済み部分の適切な位置に挿入する。
- まず、配列の先頭要素をソート済みと看做して、2番目の要素から順に処理する。
- 処理対象の要素 (key) を一時的に保持して、ソート済み部分を後ろから順に走査して、keyより大きい要素は1つ右にずらす。
- そして、最終的にkeyよりも小さい要素を見つけた位置 (または配列の先頭) の右側にkeyを挿入する。
単純挿入法 (挿入ソート) の特徴として、既にある程度ソートされているデータに対しては効率的に動作する。
これは、ソート済み部分での探索が早く終わるからである。
また、同じ値の要素の相対的な順序が保たれるため、安定なソートである。
計算量においては、最悪の場合で となるが、ほぼソートされているデータに対しては に近い性能を示す。
メモリ使用量は、ソートを配列内で直接行うことができるため、追加のメモリをほぼ必要としないというメリットがある。
#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;
}
# 出力例: ソート前の配列: 64 34 25 12 22 11 90 50 ステップ 1: 34 64 25 12 22 11 90 50 # 2番目の要素34に注目し、前の要素64と比較する。34 < 64なので、64を右にずらし、34を挿入する ステップ 2: 25 34 64 12 22 11 90 50 # 3番目の要素25に注目し、前の要素と順に比較する。25は34, 64より小さいため、これらを右にずらし、適切な位置に25を挿入する ステップ 3: 12 25 34 64 22 11 90 50 # 4番目の要素12に注目し、同様に比較と挿入を行う。12は最小値なので配列の先頭に移動する ステップ 4: 12 22 25 34 64 11 90 50 # 22を12と25の間に挿入する ステップ 5: 11 12 22 25 34 64 90 50 # 11を比較しながら移動させて、配列の先頭に挿入する ステップ 6: 11 12 22 25 34 64 90 50 # 90は既にソート済み部分の要素より大きいため、位置は変わらない ステップ 7: 11 12 22 25 34 50 64 90 # 50を64と90の間の適切な位置に挿入する ソート後の配列: 11 12 22 25 34 50 64 90