整数の選択

質問

アルゴリズムに関する質問です．

n個の相異なる整数が配列 A[1..n] に格納されていて，その配列の中からk番目に小さい整数を選ぶ問題のアルゴリズムを考えています．kは 1<=k<=n を満たす自然数であり，この選択問題は O(n) で解けるものです．

ヒープを使ったりして考えたのですがうまくいきません．どなたかこのアルゴリズムを教えてください．よろしくお願いします．

回答No.4

liar_adan · ベストアンサー

私もこの問題はソートと同じだと思いますが、
ソートのアルゴリズムは大抵O(n^2)かかるものであり、
O(n)で解けというのはかなり制約になります。

単純ソートを使ってしまうとO(n^2)になり、
ヒープソートやクイックソートだとO(n*log(n))になってしまいます。
O(n)でできるソートはあまり多くありません。
それでもたとえば「ビンソート」というのがあります。

・まず、配列をサーチして、最大値を選ぶ(nに比例)、
・配列B[1..maxA]を確保。
・もう一回配列Aをサーチして、B[A[x]]にフラグを立てる。(nに比例)
・配列Bを下からサーチして、k番目に小さい
(フラグが立っているk番目の)数を見つける。(最大でnに比例)

ただし、見てもらえばわかる通り、最大値が大きいと
必要なメモリがそのまま多くなってしまい、実用的ではありません。

O(n)のアルゴリズムは、参考URLの
『定本　Cプログラマのためのアルゴリズムとデータ構造』
近藤嘉雪著　ソフトバンクパブリッシング発行
に3種類記述されています。

参考URL：

http://www.amazon.co.jp/exec/obidos/ASIN/4797304952/

お礼

ビンソートを使って解くことが出来ました．
おっしゃる通り最大値が大きいと実用的とは言え
ませんが，今回はメモリを意識する必要がないよう
なので，ビンソートが有効です．
ありがとうございました．

回答No.3

imogasi

ヒープを積んで、積み終わり、根から１つづつ（ソート後の）データを順次取り出す時、ｋ個目で止めれば良いのでは。
あるいはいっそのことソート後に、A(K)を取れば良いのではないですか。
この問題は実質ソートと同じことでしょう。ソートをしないでｋ番目が判るアルゴリズムがあるとは、私の力では予想できないです。

回答No.2

tsukasa-12r

一つ考えてみました。
(1) まず、配列 A[1...n] とは別に、配列 F[1...n] を用意します。配列 F[1...n] の各要素を全て 0 で初期化します。
(2) A[1...n] の中から最小値 A[i] を求め、A[i] は使用済み、という意味で、F[i] に 1 をセットします。
(3) A[1...n] の中で、対応する F[1...n] が 0 のものの中から最小値を求め、(2) 同様に、最小値 A[j] に対して F[j] に 1 をセットします。
この手順を繰り返して、k 番目に小さい値を取得します。
説明のために
(1) → (2) → (3)
と書きましたが、実際には
(1) → (3) → (3) → ...
と (3) を k 回繰り返せば k 番目に小さい整数を取得できます。

C で書いてみました。
#include <stdio.h>

const CINT_N = 10;

int a[] = { 315, 130, 3, 27, 85, 9, 17, 83, 51, 38 };

void main()
{
　　int f[CINT_N];
　　int iMin;　　　　　/* 最小値 */
　　int iInitMin;　　/* 暫定の最小値がセットされたとき 1 */
　　int iIndex;　　　/* 最小値を指すインデックス */
　　int i, j, k;

　　/* f[1...n] を初期化 */
　　for( i = 0; i < CINT_N; i++ ) {
　　　　f[i] = 0;
　　}

　　/* 例として、3 番目に小さい整数を求める */
　　k = 3;
　　for( j = 1; j <= k; j++ ) {
　　　　iInitMin = 0;
　　　　for( i = 0; i < CINT_N; i++ ) {
　　　　　　if( f[i] == 0 ) {
　　　　　　　　if( iInitMin == 0 ) {
　　　　　　　　　　iMin = a[i];　　/* 暫定の最小値をセット */
　　　　　　　　　　iIndex = i;
　　　　　　　　　　iInitMin = 1;
　　　　　　　　} else {
　　　　　　　　　　if( a[i] < iMin ) {
　　　　　　　　　　　　iMin = a[i];
　　　　　　　　　　　　iIndex = i;
　　　　　　　　　　}
　　　　　　　　}
　　　　　　}
　　　　}
　　　　/* j番目に小さい整数に対して使用済みのフラグをセットする */
　　　　f[iIndex] = 1;
　　}

　　printf( "%d 番目に小さい整数は %d です。\n", k, iMin );
}

お礼

ありがとうございます．これでk番目に小さい
整数を得ることができますね．
ただ今回の問題では "O(n)" で解くことが必要です．
このプログラムでは計算時間が O(n^2)になって
しまうように思います．
でも本当に丁寧に回答してくださり，ありがとうございました！

回答No.1

tsukasa-12r

＞ヒープを使ったりして…
というのはヒープソートのことでしょうか？

一旦、ソートして、ソートした結果を
配列 B[1...n] に格納してやれば B[k] が求める整数になると思うんですけど。