選択ソート - 最小/最大のインデックス

Question

私はcprogramming.com の選択ソートアルゴリズムを見ていましたが、実装にエラーが見つかりました。

アルゴリズムを使いこなすと、 "index_of_min"という変数があります。これは "index_of_max"でなければならないと思います（テストしたときに最大から最小にソートされています）。

これはタイプミスやマイナーミスであると考えて、wikipediaなどの他のウェブサイトや、geekpediaなどのよく知られていないウェブサイトをチェックアウトしました。彼らはそれをminのインデックスと呼ぶようです。

デバッガで実行したとき、実際には最大値のインデックスになっていたようでした。私はどこかでミスをしていますか？

編集：Svanteが指摘したように、プログラミングの暗示だけが間違っています。 WikipediaとGeekpidiaは問題ありません。

Answer 1

wikipediaとgeekpediaのサイトは正しいようですが、cprogramming.comの実装には実際にバグがあります。この：

if (array[index_of_min] < array[y]) 
    { index_of_min = y; } 

は順序が逆転しており、それは次のようになります。もう一つの修正は、変数index_of_maxを呼び出すことが、私は、ソートのアルゴリズムは、最大に最小をソートするために期待する、とあればなり

if (array[y] < array[index_of_min]) 
    { index_of_min = y; } 

この期待は（私が推測しているように）プログラマの大多数によって共有されていますが、最小の驚きの原則はむしろ上記の修正を要求します。

Answer 2

あなたは正しいです。そのウェブサイトのコード（下記参照）が間違っています。内側ループの終わりに

for(int x = 0; x < n; x++) 
    { 
     int index_of_min = x; 
     for(int y = x; y < n; y++) 
     { 
      if(array[index_of_min] < array[y]) /* Here's the problem */ 
      { 
       index_of_min = y; 
      } 
     } 
     int temp = array[x]; 
     array[x] = array[index_of_min]; 
     array[index_of_min] = temp; 
    } 

、for(int y=x; y<n; y++)、変数、index_of_min、最大値のインデックスを保持します。アレイがから最小配列にソートされるように設計されたがであると仮定すると、これはという不十分な名前のです。

あなたは、配列が（予想されるように）最大の最小をソートし、あなたがif文逆にする必要がある場合：

if (array[y] < array[index_of_min]) 
{ 
    index_of_min = y; 
} 

が

ロバートC. Cartaino

、お楽しみに

Answer 3

コードを読み取っただけですが、正しいと思われます。index_of_minのいずれかが間違っているか、比較が後方にあります。

いくつかの箇所でこのエラーが発生しているように見えるかもしれません。それぞれが単一の共通ソースからコピーされる可能性が非常に高いです。

Answer 4

よりプログラミングから。com "これは、配列の要素を大小にソートしたい場合は、配列の先頭に配置する最小のもの（または最大のもの）を選択することで機能します。「大小からソートするのでコードが間違っていますまた、変数の命名でもない場合、index_of_minは配列（0）の開始点を追跡し、その配列内を前方に移動します。 index_of_minは最小のインデックス値を保持します。そのインデックスに値が何であれ混乱させないでください。