sorting - 凸包アルゴリズムを使用して整数をソートする

Question

2 次元の凸包のアルゴリズムでは、並べ替えが使用されます。誰かが凸包をブラック ボックスとして実装したライブラリを提供したとします。凸包アルゴリズムを使用して、与えられた整数のシーケンスを並べ替える方法を示してください。「ブラック ボックス」という言葉は、コードの内部を調べないことを意味します。入力と出力が何であり、結果がどのように見えるかしかわかりません。凸包のライブラリ実装から「並べ替えアルゴリズムを引き出す」ことはできません。凸包アルゴリズムをプリミティブ ステップとして呼び出すことができると想定できます。

Answer 1

整数 n=|A| の入力シーケンス A=[x1,...,xn] からの各 xi に対して、対応する点 (xi, xi^2) を作成し、2D 空間で n 個の点を構成します。このような点は、凸曲線である放物線を形成します。線形時間では、点を検査して最も左の点 pl を検出できます。次に、点 pl から開始して凸包を右にトラバースして、数値 x1、...、xn の並べ替えられた順序を生成できます。

Ω(n logn) は比較ベースのソートの下限であるため、凸包はそれよりも少なくないと主張することができます。

Answer 2

整数を x 軸上にある点として扱います (つまり、y 座標はゼロです)。ポイントを凸包アルゴリズムにフィードします。アルゴリズムがこの縮退したケースを処理できるほど堅牢でない場合は、各整数を 2 つの点 (x, 1) と (x, -1) にします。アルゴリズムの出力として、閉ループ (ポリゴン) を形成するポイントを取得します。移動して最小の x を持つポイントを見つけます。その後、ポイントの増加する x 値がソートされた整数を表します。

繰り返しになりますが、凸包アルゴリズムが同じ直線上にある境界点を処理する際に問題がある場合は、y 値に 2 乗整数を使用して凸性を強調します。これはもちろん、すべての整数が負でない場合です。負の整数がある場合は、y 値の平方を計算する前に最小値を減算する必要があります。