目次から探す
バブルソートの概要
バブルソートは、要素の比較と交換を繰り返すことで、配列を昇順または降順にソートするアルゴリズムです。
隣り合う要素を比較し、必要に応じて交換することで、大きい値を配列の末尾に移動させることが特徴です。
バブルソートの特徴
- 単純なアルゴリズムで実装が比較的容易です。
- 安定なソートアルゴリズムであり、同じ値を持つ要素の順序が変わることはありません。
- 要素の数が多い場合や、要素の並びが逆順になっている場合には効率が悪くなる傾向があります。
バブルソートのアルゴリズム
- 配列の先頭から順に隣り合う要素を比較します。
- 左側の要素が右側の要素より大きい場合、両方の要素を交換します。
- 交換が行われた場合、交換が行われなくなるまで1から2の手順を繰り返します。
- 1回のパスが終了すると、配列の末尾には最大値が配置されます。
- 2から4の手順を配列の要素数-1回繰り返します。
これにより、配列がソートされます。
バブルソートの実装方法
バブルソートの基本的な実装方法
バブルソートを実装するためには、2つのループを使用します。
外側のループはパスの回数を管理し、内側のループは隣り合う要素の比較と交換を行います。
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 要素の交換
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}バブルソートの最適化方法
フラグを用いた最適化
バブルソートは、配列が既にソートされている場合でも、全てのパスを繰り返すため効率が悪くなります。
そこで、フラグを用いてソートが行われたかどうかを判定し、ソートが行われなかった場合にはループを終了する最適化があります。
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// ソートが行われたかどうかを判定するフラグ
int sorted = 1;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 要素の交換
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
sorted = 0;
}
}
// ソートが行われなかった場合、ループを終了する
if (sorted) {
break;
}
}
}ソート範囲の狭め方による最適化
バブルソートでは、パスごとに最大値が配列の末尾に配置されるため、末尾の要素はソート済みとみなすことができます。
そのため、内側のループの範囲を狭めることで、比較回数を減らすことができます。
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
// ソートが行われたかどうかを判定するフラグ
int sorted = 1;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 要素の交換
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
sorted = 0;
}
}
// ソートが行われなかった場合、ループを終了する
if (sorted) {
break;
}
}
}バブルソートのサンプルコード
サンプルコードの解説
以下のサンプルコードは、バブルソートを実装したものです。
配列の要素をランダムに生成し、バブルソートを適用して昇順にソートします。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void bubbleSort(int arr[], int n) {
// バブルソートの実装
// ...
}
int main() {
// 乱数のシードを設定
srand(time(NULL));
// 配列の要素数を指定
int n = 10;
// 配列の要素をランダムに生成
int arr[n];
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100;
}
// ソート前の配列を表示
printf("ソート前: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// バブルソートを適用
bubbleSort(arr, n);
// ソート後の配列を表示
printf("ソート後: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}サンプルコードの実行結果
以下は、上記のサンプルコードを実行した結果の例です。
ソート前: 87 12 45 67 23 56 78 34 90 10
ソート後: 10 12 23 34 45 56 67 78 87 90このように、バブルソートを適用することで、配列が昇順にソートされました。
