ブログの名前なんて適当で良いのでは

説明を求めるな、記事を読め

【復習】バブルソート

競技プログラミングの勉強を始めようと思い、とりあえずバブルソートを再度学んでみた。これは隣接する二つの配列の要素を比較して、並び替えるソーティングである。計算量はO(n^2)。ここまではまぁ知っている内容だったのだが、このバブルソートの交換回数は、反転数と呼ばれ、その配列の乱れ具合を示す指標らしい。

 また、バブルソートは安定なソートと言われ、比較内容が同じ内容であったときに順番を変更しないというソートである。これを利用して、作成したソートが安定であるかどうかは、バブルソートの結果を用いて行うことができるので、要素数N、つまりO(N)で調べることができる。

gist4364353f3dd0e9b842e3