ソートの平均比較回数と転倒数

互いに異なる $7$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[7]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,6$ の順に、$j=1,2,\dots ,7-k$ の順で $A[j]$ と $A[j+1]$ を比べ、$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

最初の並びは、$7$ 個の数の $7!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

$1,2,\dots ,10$ を $1$ 列に並べた配列 $A[1],A[2],\dots ,A[10]$ がある。並び方は $10!$ 通りのどれも同様に確からしいとする。この配列を、次のバブルソートで昇順に並べかえる。

$i=1,2,\dots ,9$ の順に、各 $i$ について $j=1,2,\dots ,10-i$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を入れかえ（交換し）、そうでなければ何もしない。

このバブルソートで行われる交換の回数の期待値を求めよ。

互いに異なる $10$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[10]$ を、次のバブルソートで昇順に並べかえる。

$k=1,2,\dots ,9$ の順に、各 $k$ について $j=1,2,\dots ,10-k$ の順に次の操作を行う：$A[j]>A[j+1]$ ならば $A[j]$ と $A[j+1]$ を交換する。

入力の並びは $10!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

互いに異なる $6$ 個の数を並べた配列 $A[1],A[2],\dots ,A[6]$ を、次の挿入ソートで昇順に並べかえる。

$i=2,3,\dots ,6$ の順に、次の操作を行う。$x=A[i]$ とし、$j=i-1$ から始めて、$j\geqq 1$ である間「$A[j]$ と $x$ を比較し、$A[j]>x$ ならば $A[j]$ を $A[j+1]$ に移して $j$ を $1$ 減らす。$A[j]<x$ ならばそこで止める」をくり返す。止まったとき（または $j=0$ になったとき）、$A[j+1]=x$ とする。

ここで、数どうしの比較（$A[j]$ と $x$ の比較）だけを数え、$j\geqq 1$ かどうかの判定は数えない。最初の配列が $6$ 個の数の $6!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

互いに異なる $6$ 個の実数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の列はそのまま返す。
• 長さ $k\ge 2$ の列は、前半の $\lceil k/2\rceil$ 個と後半の残り $\lfloor k/2\rfloor$ 個に分け、それぞれを再帰的に昇順に並べかえてから、次の手続きで併合する。
• 併合の手続き: 昇順に並んだ $2$ つの列 $P,Q$ が与えられたとき、どちらも空でない間は、$P$ の先頭と $Q$ の先頭を $1$ 回比較し、小さい方を取り出して出力の末尾に加える。一方の列が空になったら、もう一方の列に残っている要素を、比較を行わずにそのまま順に出力の末尾に加える。

入力の $6$ 個の数の並び方は $6!$ 通りすべてが等確率で現れるとする。このマージソート全体で行われる要素どうしの比較回数の期待値を求めよ。

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の配列はそのまま返す。
• 長さ $2k$（$k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
• マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。