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

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

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

ピボットの選択は毎回ほかの選択と独立に行うものとする。数どうしの比較は上の「ピボットと残りの数との比較」だけで行われるとき、$4$ 個の数を並べ終えるまでに行われる比較の回数の期待値を求めよ。

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

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

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

互いに異なる $7$ 個の実数からなる集合を、次の乱択クイックソートで昇順に並べかえる。

• 大きさ $2$ 以上の集合 $S$ を処理するときは、$S$ の要素から $1$ 個をピボット $p$ として等確率で選ぶ。$p$ を $S$ のほかのすべての要素とそれぞれちょうど $1$ 回ずつ比較し、$S$ を $p$ より小さい要素の集合 $S_{-}$ と $p$ より大きい要素の集合 $S_{+}$ に分ける。そのあと、$S_{-}$ と $S_{+}$ をそれぞれ同じ方法で処理する。
• 大きさ $0$ または $1$ の集合を処理するときは、何もしない（比較を行わない）。

ピボットの選択はそれぞれ独立に行うものとする。最初の集合 $7$ 個全体を処理し始めてから終わるまでに行われる比較のうち、小さい方から $3$ 番目の要素がかかわる比較の回数の期待値を求めよ。

互いに異なる $5$ 個の数が入った配列から、小さい方から $3$ 番目の数（中央値）を、次の乱択選択アルゴリズム（乱択クイックセレクト）で求める。

• 現在の候補の集合を $X$ とし、最初は $X$ を $5$ 個の数全体とする。また、求めたい順位を $k=3$ とする。
• $X$ の要素が $1$ 個だけなら、それを答えとして終了する（比較は行わない）。
• そうでなければ、$X$ の要素から $1$ つを等確率で選んでピボット $p$ とし、$p$ を $X$ のほかのすべての要素と $1$ 回ずつ比較して、$p$ より小さい要素の集合 $L$ と大きい要素の集合 $R$ に分ける（このとき比較は $|X|-1$ 回行われる）。
• $|L|=k-1$ なら $p$ を答えとして終了する。
• $|L|\ge k$ なら、$X$ を $L$ に置き換えて（$k$ はそのまま）最初の手順に戻る。
• $|L|\le k-2$ なら、$X$ を $R$ に、$k$ を $k-|L|-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!$ 通りの並べ方が同様に確からしいとする。このとき、ソートが終わるまでに行われる交換の回数の期待値を求めよ。