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

互いに異なる $6$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[6]$ から、最大値と最小値の両方を次のアルゴリズムで求める。

• 最初に $mx=A[1]$、$mn=A[1]$ とする。
• $i=2,3,\dots ,6$ の順に、次の操作を行う。
• まず $A[i]$ と $mx$ を比較する。$A[i]>mx$ であれば $mx=A[i]$ とし、この $i$ についての操作を終える。
• そうでなければ、$A[i]$ と $mn$ を比較し、$A[i]<mn$ であれば $mn=A[i]$ とする。

$6$ 個の数の並び方は $6!$ 通りすべてが等確率 $\frac{1}{6!}$ で起こるとする。このアルゴリズムで行われる要素どうしの比較の回数の期待値を求めよ。

互いに異なる $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!$ 通りの並べ方のどれであるかが同様に確からしいとき、比較回数の期待値を求めよ。

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

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

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