なぜ選択ソートは、私が選択ソートは、ブルートフォース戦略を使用していることを見出した

Question

貪欲ではありません。しかし、私は貪欲戦略を使っていると思う。

は、なぜ私はそれは貪欲使用していることだと思います：それはそれ外側のループでのn-0から1になり、I + 1のn-1から。これは本当に素朴です。それは、繰り返しごとに1つの最小要素を選択します。局所的に最適な要素が選択されます。貪欲のようなものはすべてですが、そうではありません。それは私がどのように考えるかではない理由

あなたは私を説明していただけますか？私がインターネットで見つけられていないこの問題に関する情報。

Answer 1

ようintgersのリストとする：A = [5、4、3、6、1、2、7]

は、貪欲アルゴリズムは、したがって、最も有望な方向を探します：

を

1. 我々は比較されます：、4から5に4が5よりも確かに小さいことがわかり、私たちの最小
2. が3に4を比較すると4を設定して、今、私たちは3〜6を比較すると、ここで
3. 私たちの最低限として3を設定しますトリッキーな部分です：通常の選択ソート（ブルートフォース）では、残りの数字を貪欲なアプローチでは、最小限の3をとり、残りの数字は考慮しません。したがって、「最高のローカル」です。

ので、このアプローチを使用してソートされたリストのようなソートされたリストになりますに： [3、4、5、1、2、7]

Answer 2

貪欲とブルートフォースアルゴリズムの異なる特徴を記述。

欲張りは、各ステップのアルゴリズムがローカルでのいくつかのオプションを選択することを意味します。つまり、先読みはありません。

ブルートフォースは、アルゴリズムがすべてを考慮して簡単な方法でオプションを探すことを意味します。例えば。バイナリ検索で要素を検索するかもしれませんし、もうブルートフォースではありません。

だから、このアルゴリズムは、貪欲とブルートフォース両方かもしれません。これらの性質は互いに排他的ではありません。

Answer 3

選択ソートは、実際にそれという意味で、貪欲アルゴリズムとして説明され得る：

一定の尺度（「sortedness」を最適化出力（その入力の順列）を選択しようと
• 、 （例えば、inversionsの数で測定することができる）、および
• のように、より小さいサブ問題（選択ソートの場合、出力順列のk番目の要素を見つけて）を局所的に選んで各サブ問題に対する最適解

同じように、他のほとんどのソートアルゴリズムにも同様の説明を適用できます。—唯一の違いはサブ問題の選択です。例えば：

• 挿入ソートローカルK最初の入力要素の順列のsortednessを最適化します。
• バブルソートは、要素の隣接するペアのソートを最適化します。グローバル最適化に到達するためには、リストを何回か反復する必要がありますが、これはまだ貪欲アルゴリズムの広い定義に含まれています。
• マージソートは、入力シーケンスの指数関数的に増加するサブシーケンスのソートを最適化します。
• quicksortは、入力を任意に選択したピボットの両端のサブシーケンスに再帰的に分割し、各ステージでソートを最大にするように除算を最適化します。

確かに、私の頭の上から、私はがは、この意味で貪欲ではないことを任意の実用的なソートアルゴリズムを考えることはできません。 （Bogosortはそうではありませんが、実用的とはほとんど言えません）さらに、これらのソートアルゴリズムを貪欲な最適化問題として定式化すると、ソートアルゴリズムを比較するとき実際に重要な細部があいまいになります。

このように、欲張りは技術的には有効だが実用的に役に立たないので、選択分類やその他のソートアルゴリズムの特徴付けは、本当に有用な情報を提供しないためだと思います。