Complexity Analysis
Coddyの「バブルソート」コースのレッスン 5/11。
バブルソートの計算量解析。
時間計算量は、実行される比較と入れ替え（スワップ）の回数に依存します。
n 回のパスを実行する必要があり、各パスで (n-1) 回の比較を行います。ここで、n はリスト内の要素数です。
合計比較回数=(n-1)+(n-1)+(n-1)....n 回
=n*(n-1)
=n2-n
バブルソートアルゴリズムの時間計算量は O(n2) です。
空間計算量について言えば、このアルゴリズムでは余分なスペースは使用されず、インプレース（in-place）ソートが実行され、要素は元のリスト自体の中で並べ替えられます。
バブルソートアルゴリズムの空間計算量は O(1)（定数） です。
チャレンジ
簡単配列とその配列のサイズを受け取る、count_swapsという名前の関数を作成してください。その配列に対してバブルソートアルゴリズムを実行し、スワップ（入れ替え）が行われた回数をカウントしてください。
自分で試してみよう
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// ここにコードを記述してください
return 0;
}
バブルソートのすべてのレッスン
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm