Adaptivity
Coddyの「バブルソート」コースのレッスン 6/11。
バブルソートアルゴリズムの時間計算量について説明しました。それは O(n2) です。しかし、配列がすでにソートされている場合はどうなるでしょうか？その場合でも、実行時間は O(n2) かかります。
アダプティビティ（適応性）とは何でしょうか？
アダプティブアルゴリズムとは、与えられた入力シーケンスに応じて動作を変化させるアルゴリズムのことです。
では、バブルソートはアダプティブなのでしょうか？
はい、バブルソートアルゴリズムをアダプティブにすることができます。アダプティブにするためには、バブルソートアルゴリズムを、最悪の場合の実行時間が O(n2)、最良の場合が O(n) となるように記述する必要があります。ここで、最良の場合とは、配列がすでにソートされている場合を指します。
boolean型のフラグ変数を使用してwhileループを制御し、すでにソートされている場合にアルゴリズムが早期に終了するようにします。
while(flag)
{
//code
}
配列がソートされるまでパスを繰り返す必要があります。スワップの回数をカウントする方法はすでに学習したので、フラグを実装して、パス内でスワップが必要ないかどうかを確認し、ループを抜けることができます。
チャレンジ
中級配列とそのサイズを受け取る、ad_bubblesortという名前の関数を作成してください。アダプティブ・バブルソート（適応型バブルソート）アルゴリズムを実行します。スワップが発生したかどうかを確認するために、flagという名前の変数を使用することを忘れないでください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// ここにコードを書いてください
*returnSize = n;
return arr;
}
バブルソートのすべてのレッスン
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm