【C言語】第8章第2回：ソートアルゴリズム：バブルソートと選択ソート
ソートアルゴリズムは、データを順序付けて整理するための基本技術です。本記事では、バブルソートと選択ソートの仕組みと実装方法を学びます。
0. 記事の概要
この記事を読むメリット
- 基礎から始める：基本的なソートアルゴリズムを理解できます。
- 実践的なスキル：データ処理の効率を向上させるソート技術を習得できます。
- アルゴリズムの応用：他のソート手法への理解を深める基礎になります。
この記事で学べること
- バブルソートの仕組みと実装
- 選択ソートの仕組みと実装
- 効率性の比較と応用例
活用のイメージ
ソートアルゴリズムは、データ分析や表示順序の最適化など、あらゆる場面で役立ちます。
1. バブルソート
1.1 バブルソートとは？
バブルソートは、隣接する要素を比較し、順序が間違っている場合に入れ替えることで、データをソートするアルゴリズムです。
例：
元のデータ：[5, 3, 8, 1, 2]
1回目のループ後：[3, 5, 1, 2, 8]
1.2 バブルソートの実装
#include <stdio.h>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 入れ替え
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
動作解説
- 外側のループ：ソートが必要な回数を決定します。
- 内側のループ：隣接する要素を比較し、順序が正しくない場合に入れ替えます。
- 結果の出力：ソートされた配列を出力します。
2. 選択ソート
2.1 選択ソートとは？
選択ソートは、最小（または最大）の要素を探して、現在の位置と交換することでソートを行います。
例：
元のデータ：[5, 3, 8, 1, 2]
1回目の交換後：[1, 3, 8, 5, 2]
2.2 選択ソートの実装
#include <stdio.h>
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 最小値を交換
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
int size = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, size);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
動作解説
- 外側のループ：現在のソート位置を決定します。
- 最小値の探索：現在位置から配列の末尾までを調べ、最小値のインデックスを取得します。
- 交換：見つかった最小値を現在の位置と交換します。
3. 練習問題
以下の課題に挑戦して、ソートアルゴリズムの理解を深めましょう。
- 選択ソートを改良して、昇順と降順の切り替えを可能にしてください。
- バブルソートを改良して、早期終了を実装してください。
- 配列内の重複を除去し、ソートするプログラムを作成してください。
4. 練習問題の解答と解説
問2の解答
#include <stdio.h>
void bubbleSortOptimized(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int swapped = 0; // 交換が発生したかどうかを記録
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) {
break; // 交換が発生しなければ終了
}
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSortOptimized(arr, size);
printf("Sorted array: ");
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
return 0;
}
このプログラムでは、交換が発生しない場合にループを早期終了することで、効率を向上させています。
5. まとめ
本記事では、バブルソートと選択ソートの仕組みと実装方法を学びました。次回は、さらに効率的なソートアルゴリズムについて学びます。