何がしたいのか
例えばこんな感じのグラフがあるとする。（雑でごめんなさい）
求めたいのは、このグラフが理想的な並びにどこまで近いか、というものです。
理想的な並びと正解率
今回は赤と青、この二種類のみのグラフを想定します。
例として、正解率100%の並び（理想の並び）とその真逆の正解率0%の並びの図です。見たまんまですが、赤色と青色が逆になっています。ここでは極端な例なので0%と100%のみですが、以下のようなグラフではどうでしょうか。
このグラフが、正解率100%の並びとどれだけかけ離れているか、それを求めればこのグラフの正解率がわかると考えました。
結論
で、正解率っぽい率になります。説明は↓へ
算出方法
言語はpythonでやっています。
お題にもあるように、算出にバブルソートを用いました。バブルソートでどうやって求めるのか…それは、ソートで移動した回数、 スワップ数をもとに計算します。
スワップ数を求める
ここでは2種類のスワップ数を求めます。
ソート時に要したスワップ数 と 最悪何回入れ替えが発生するかの最大スワップ数 です。
ソートに要したスワップ数
まずこのスワップ数を求めます。要はソートすればいいだけです。何回でソートできたかを調べます。
引数rowはソート前のグラフの並びを0,1で置き換えたlistです。
def swap_count(row):# 必要スワップ回数
count = 0
for j in range(len(row)):
for i in range(1, len(row)-j):
if row[i-1] > row[i]:
row[i-1], row[i] = row[i], row[i-1]
count += 1
return count
最悪スワップ数
最悪何回の入れ替えが発生するか、入れ替えにかかる回数の最大値を求めます。Counterを使用しています。
from collections import Counter
def max_count(row): # 最高スワップ回数
c = Counter(row)
assert len(c.values()) == 2 # ２種類のみ通すよ
l_len = len(row)
max_cnt = 1
for v in c.values():
max_cnt *= l_len - v
return max_cnt
２つのスワップ数から正解率を求める。
結論の式の通り、実際のソートで発生したスワップ数を最悪スワップ数で割り、それを100%から差し引くだけです。
特徴として、この式では正解率はマイナス値になりません。
おわり
何かと使えるかなと思いメモとして残しました。異論受け付けます。