k番目に小さい数を出力する選択アルゴリズム

Question

k番目に小さい数を出力する選択アルゴリズムのプログラムがわかりません
再帰を使ってやるらしいのですが全くわかりません
どなたか教えてください！

Comments

[hentaiman]

再帰を使えっていう課題なんでしょうかね？

Answer 1

ソートアルゴリズムは色々とありますが、
普通にソートをすれば、あとは k 番目に小さい値を取れば終了です。

例えばリストをクイックソートをして、k 番目に小さい値を取るというのは簡単そうです。
これも再帰を使っています。

• pythonでquicksort

ただ、恐らく題意としては、
二分ヒープを使って欲しいのかなと推測しています。

なぜなら全部をソートしなくても k 番目に小さい値を取れるので、
全てをソートするのに比べて、計算量が少し少なくて済むからです。

リストを heapify して、そのあと heappop を k 回せばいけますね。
heapify, heappop 共に再帰を使用しています。

#
# 対話モード >>> にコピペで
# 実行できます。
#
from heapq import heapify, heappop
heap = [3, 9, 4, 1, 6, 8, 0, 5, 2, 7]

# heapify
heapify(heap)

# heappop
k = 3
for _ in range(k - 1):
    heappop(heap)

print(heappop(heap))

>>> print(heappop(heap))
2
>>>

ソースコードは、ここ。

• heapq.py

ソースコードの解説は、ここ。

• 二分ヒープ

ただこれだけでは説明が足りないかなと思います。
友達に相談して、乗り切ってください笑

Answer 2

k番目に小さい数を知るためには、その数より小さい数をk-1個みつけて、他にはその数より小さい数がないという判断をしないといけません。
ということで、全体を昇順にソートして、そのk番目を見るということになります。
再帰は使う必要が無くて、ソートすればいいだけです。