(javascript) 与えられた配列の中からi番目に大きいものを取り出すアルゴリズム

[kanata]

本当に申し訳ないのですが、期限が今日までなので、できればプログラム自体を教えて欲しいです。

以下の問題をやれるところまでやったのですが、あとどう書き加えれば完成するのか息詰まってしまい、困っています。javascriptが分かる方、助けてください。

問題
与えられた配列 a の中の i 番目に大きな要素を取り出すために以下のようなアルゴリズムを考える．このアルゴリズムを実現せよ．この関数をkadai(a, i)とせよ．keyはaを用いて適当に設定せよ.

コード:

function kadai(a, i){
if (a.length <= 1) return a[0]
else {
あるkeyを設定して，
a の要素を> key と<= key の部分に分離する．
それぞれをa1, a2 とおく．
if (a1.length < i) return kadai(a2, i - a1.length)
else return kadai(a1, i)
}
}

自力ではここまでやりました。
[codeJScript]
function kadai(a, i)
{
if (a.length <= 1) return a[0]
else
{
var key = Math.floor(Math.random() * a.length)
var a1 = []
var a2 = []

if (a1.length < i) return kadai(a2, i - a1.length)
else return kadai(a1, i)
}
}
var a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
puts(a)
puts(kadai(a, 2))
[/code]

ちなみに、完成すると以下のような出力になるみたいです。
[出力]
1,2,3,4,5,6,7,8,9
3

[kanata]

自力のプログラムがコード形式で反映されてなかったため、再掲載します。

コード:

function kadai(a, i)
{
if (a.length <= 1) return a[0]
else 
{
var key = Math.floor(Math.random() * a.length)
var a1 = []
var a2 = []

if (a1.length < i) return kadai(a2, i - a1.length)
else return kadai(a1, i)
}
}
var a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
puts(a)
puts(kadai(a, 2))

[かずま]

自力のプログラムがコード形式で反映されてなかったため、再掲載します。

プログラムの全部の行を左詰めで書くのはなぜですか？

var a = [33, 11, 44, 22] の場合についてお尋ねします。
puts(kadai(a, 2)) で何が表示されることを期待していますか？
key の値はどんな範囲ですか？
その key を配列 a の要素と比較することに意味がありますか？

[YuO]

日本語の文から，

• key : aの要素の中の，最大でも最小でもない値
• a1 : aの中でkeyより大きい値を持つ要素
• a2 : aの中でkey以下の値を持つ要素

という風に分解すればよいわけです。

まず，ここで利用するkeyはaの各要素の値と比較するものなので，aの要素数から決定してはいけません。
aの要素の値から選ぶようにします。
ただし，a[0]を常に使うような形にすると，a[0]が最大値の場合にa1が常に空でa2が残り全てとなってしまうようなことがあるためよい結果が得られません。
a[0]とa[a.length - 1]の平均を使うなど，常に同じ値がkeyにならないように注意する必要があります。

次に，a1とa2について，文章では先に分離してそれに名前をつけているように書いていますが，実際にはaの各要素を調べていって，どちらの条件に合うかを調べて，a1またはa2の配列に追加していくことになります。
各要素を調べるにはfor文を使い，配列への追加はpushを使います。
JavaScriptに慣れた人であればfilterを使って処理することもありますが，課題のようなので素朴なループと配列追加の方がよいでしょう。