08/05/02 18:46:15
どなたかこの問題を解いて下さい。
下は0からM-1までの正整数が入った長さNの配列を分布数え上げ(カウンティング)ソートするアルゴリズムである。
以下の問いに答えよ。
プログラム
for (int i=0; i< M; i++) C[i] = 0;
for (int i=0; i< N; i++) C[value[i]] ++;
for (int i=1; i< M; i++) C[i] += C[i-1];
for (int i=N-1; i >= 0; i--) sorted[--C[value[i]]] = value[i];
（1）配列Cの役割を記せ。
（2）プログラム３行目の処理目的を記せ。
（3）プログラム４行目においてiを昇順でなく降順に変化させsorted配列を作成する目的は何か。
（4）このプログラム実行に要する計算量をM, Nを用いて表せ。
（5）一般にn個の要素のソーティングに要する計算量が少なくともO(n log n)かかる理由を説明せよ。必要であれば、スターリングの公式用いてよい。