アルゴリズムと計算量の問題

$1,2,3,4,5,6$ を $1$ 列に並べる $6!$ 通りの並べ方から $1$ つを等確率で選び、それを配列 $A[1],A[2],\dots ,A[6]$ とする。$1\le i<j\le 6$ を満たす整数の組 $(i,j)$ で $A[i]>A[j]$ となるものを「転倒」とよぶ（転倒の個数は、挿入ソートで隣り合う要素を交換する回数に等しいことが知られている）。配列 $A$ に含まれる転倒の個数を $X$ とするとき、期待値 $E[X]$ を求めよ。

互いに異なる $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!$ 通りの並べ方のどれもが同様に確からしいとする。このソートで行われる交換の回数の期待値を求めよ。

互いに異なる $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!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。

$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]$ を入れかえ（交換し）、そうでなければ何もしない。

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

互いに異なる $4$ 個の数が入った配列を、次の乱択クイックソートで小さい順に並べる。

• 並べる対象の数が $0$ 個または $1$ 個のときは、何もせずに終わる（比較は行わない）。
• 対象の数が $m$ 個（$m\ge 2$）のときは、その $m$ 個の中からピボットを $1$ 個、等しい確率 $\frac{1}{m}$ で選ぶ。ピボットを残りの $m-1$ 個のそれぞれと $1$ 回ずつ比較し（比較は $m-1$ 回）、ピボットより小さい数の組と大きい数の組に分ける。それぞれの組に対して、同じ手順を繰り返す。

ピボットの選択はすべて互いに独立に行われるものとする。このとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。