32 匹のウサギがいて、それぞれ体重が違うので、体重で並べ替えたいと思います。一度に 2 匹のウサギの重さを量り、どちらのウサギが軽いかを教えてくれるおもりを使うことができます。すべてのウサギを並べ替えるために必要な比較の最小数は何ですか?また、どのアルゴリズムを使用しますか?
たとえば、クイックソートを使用する場合、32*32 (最悪の場合は n^2) の比較を行う必要がありますが、これはおそらくこの質問の比較が最も少ないアルゴリズムではありません。
1 に答える
0
クイックソートがどのように機能するかを正しく覚えていないかもしれませんが、これが私がすることです：
値のペアを取得し、それらを順番に並べ替えます（1-2、3-4など）。これにより、16個の「短いソート済みキュー」が作成されます。次に、隣接するキューについて、最上位の要素を比較します。次に、残りの上部を含む「上から1つ」。リストを下に向かって作業を続けます。これには最大3つの比較が必要です。他のペアについても繰り返します。これまでの合計=8+ 4 * 3 = 20
同じように、4セットの4つのソートされたウサギがあり、それぞれ最大7ステップで2セットの8にソートされ、さらに14になります。次に、8つの2セットを15でソートします。総数：8 + 12 + 14 + 15=49。
たった4つで表示（同じ原則）：
体重の降順でウサギABCDがあると仮定します（それはわかりません...昇順で欲しいです）。アルゴリズム：
AとBを比較-今はBA
CとDを比較-今はDC
BDを比較-Dは最も軽く、ラインの最前線に移動します
BCを比較-Cはより軽く、次の行
ここでB（Aより軽いことはすでにわかっています）を入れ、最後にAを入れます
ご覧のとおり、合計4つの比較がありました...
于 2013-03-01T05:09:41.083 に答える