Auswahl Sortierung - Index von Min/Max

Question

Ich habe durch die Auswahl Sortieralgorithmus auf cprogramming.com gesucht und ich denke, ich fand einen Fehler in der Implementierung.

Wenn Sie den Algorithmus durcharbeiten, gibt es eine Variable namens "index_of_min", von der ich glaube, dass sie "index_of_max" sein sollte (seit ich sie getestet habe, sortierte sie vom größten zum kleinsten).

Dachte, dass es ein Tippfehler oder ein kleiner Fehler war, habe ich einige andere Websites wie wikipedia und einige weniger bekannte Websites wie geekpedia ausgecheckt. Es scheint, als ob sie es Index von min nennen.

Wenn ich es durch den Debugger lief, schien es mir wirklich, dass es der Index des maximalen Wertes ist. Mache ich irgendwo einen Fehler?

Edit: Wie Svante darauf hingewiesen hat, ist nur die Programmierimplementierung falsch. Wikipedia und Geekpidia sind in Ordnung.

Answer 1

Die Websites von Wikipedia und Geekpedia scheinen korrekt zu sein, die Implementierung von cprogramming.com hat tatsächlich einen Fehler; dies:

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

hat die Reihenfolge umgekehrt, sollte es sein:

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

Ein weiterer Fix wäre die Variable index_of_max zu nennen, aber ich würde ein Sortieralgorithmus erwarten kleinsten zum größten zu sortieren, und wenn Diese Erwartung wird von der Mehrheit der Programmierer geteilt (wie ich annehme), das Prinzip des geringsten Erstaunens verlangt eher die obige Lösung.

Answer 2

Sie haben Recht. Der Code von dieser Website (siehe unten) ist falsch.

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; 
    } 

Am Ende der inneren Schleife, for(int y=x; y<n; y++), die Variable, index_of_min hält den Index des maximalen Wertes. Angenommen, es war entworfen, um das Array von größten zum kleinsten zu sortieren, ist dies eine schlecht benannte Variable.

Wenn Sie das Array wollen sortiert kleinsten zum größten (wie man erwarten würde), müssen Sie die umkehren if-Anweisung:

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

Genießen,

Robert C. Cartaino

Answer 3

Ich habe gerade erst den Code gelesen, aber es sieht so aus, als ob Sie Recht haben: entweder index_of_min ist falsch benannt oder der Vergleich ist rückwärts.

Es ist nicht so seltsam, wie es scheint, diesen Fehler an mehreren Stellen zu sehen. Es ist sehr wahrscheinlich, dass jeder von einer einzigen gemeinsamen Quelle kopiert wird.

Answer 4

Von Cprogramming.com "Es funktioniert, indem Sie das kleinste (oder das größte, wenn Sie von groß zu klein sortieren wollen) Element des Arrays auswählen und es an den Anfang des Arrays stellen" So haben sie es von groß zu klein sortiert, der Code ist falsch , noch ist die Variablen Benennung, index_of_min verfolgt den Startpunkt im Array (0) und bewegt sich dann in diesem Array. dh index_of_min behält den kleinsten Indexwert bei. Verwirre es nicht mit dem Wert, der in diesem Index liegt.