Auswahl Sortierung Abrufen falscher Index des Arrays

Question

Ich schreibe eine Auswahlsortierung, die bei einem Array ungeordneter Elemente ein neues Array mit den Indizes der sortierten Elemente füllt. falsch Zum Beispiel

[3, 2, 1] 

zurückkehren würde

[2, 1, 0] // original indexes of sorted array [1, 2, 3] 

Leider ist es das Array füllt, den gleichen Index über einen über wiederholen.

Dies ist mein Code:

void sort(float data[], int indx[], int len) { 
    int min; 
    float temp; 
    float tempData[len]; 

    for (int x = 0; x < len; ++x){ 
    tempData[x] = data[x]; 
    } 

    for (int i = 0; i < len; ++i) { 
    min = i; 

    for (int j = i + 1; j < len; ++j) { 
     if (tempData[j] < tempData[min]) { 
     min = j; 
     } 
    } 

    temp = tempData[i]; 
    tempData[i] = tempData[min]; 
    tempData[min] = temp; 

    indx[i] = min; 
    } 
} 

Und da dieses Array:

[8.5, 10.0, 9.25, 12.5, 12.75, 12.5, 16.0, 14.75, 17.0, 18.0, 21.0, 13.0, 7.25]; 

es zurück:

[12, 12, 2, 12, 5, 12, 12, 11, 11, 12, 11, 12, 12] 

Ich kann nicht, wo die Logikfehler scheinen, um herauszufinden tritt auf. Könnte mir jemand helfen, es zu finden?

Answer 1

Füllen Sie zunächst den Indx mit den Zahlen 0 bis len -1 und verwenden Sie indizierten Zugriff zum Scannen und Bearbeiten des Arrays. Ihr aktueller Code kann nicht mit der Eingabe synchronisiert werden. Und Sie brauchen nicht die tempData.

so etwas wie folgt aus:

void sort(float data[], int indx[], int len) { 
    int min; 
    float temp; 

    for(int x = 0; x < len; ++x){ 
     indx[x] = x; 
    } 

    for (int i = 0; i < len; ++i) { 
     min = i; 

     for (int j = i + 1; j < len; ++j) 
     { 
      if (data[indx[j]] < data[indx[min]]) 
      { 
       min = j; 
      } 
     } 

     temp = indx[i]; 
     indx[i] = indx[min]; 
     indx[min] = temp; 
    } 
} 

Answer 2

Es gibt ein Problem mit Ihrem Algorithmus. Angenommen, der Mindestwert befindet sich an der letzten Position. Sie speichern die letzte Position an erster Stelle Ihres Array-Index. Dann tauscht man den Wert dort mit dem Wert an erster Stelle. Ihre letzte Position könnte also das Minimum der verbleibenden Werte enthalten.

Stattdessen initialisieren Sie Ihr Array von Indizes mit {0,1,2,3,4,5,6 ...} dann sortieren Sie dieses Array auf der Grundlage der Werte der Daten in diesen Indizes.

Answer 3

Das Problem ist, dass Sie den Inhalt des Arrays nicht austauschen sollten, um die richtige Reihenfolge zu erhalten, einfach "markieren" (Sie könnten Hal's Antwort auf die Fehlererklärung sehen).

for (int i = 0; i < len; ++i) { 

    min = i; 

    for (int j = 0; j < len; ++j) { 
     if (tempData[j] < tempData[min]) { 
     min = j; 
     } 
    } 

    tempData[min]=100000000; //INF, equal to "don't compare this" 

    indx[i] = min; 
    } 

Answer 4

Die Index-Array speichert den Index der letzten Position während des Sortierverfahrens, anstelle des Originalindex: Dies sollte die rechte Ausgabe erzeugen.

initialisieren So den Index-Array mit dem ursprünglichen Index

indx[i] = i; 

Auch

indx[i] = indx[min]; 
indx[min] = i; 

Answer 5

hier ist der Logikfehler den Index während des Sortierprozesses tauschen. Jedes Mal, wenn ein Element zur Verarbeitung ausgewählt wird und eine Bewegung von seiner Position aus erforderlich ist, ändert sich der Index des Elements auch . Nach der Verarbeitung des ersten Elements (8.5) mit dem Index 0 wird es in den Index der kleinstes Element bei Index 12 und so weiter. die Lösung, die die Verwendung von "Flags" beinhaltet scheint angemessen