Selezione ordinamento recupero indice errato dell'array

Question

Sto scrivendo un ordinamento di selezione che, data una matrice di elementi non ordinati, riempirà un nuovo array con gli indici degli elementi ordinati. Ad esempio,

[3, 2, 1] 

ritornerebbe

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

Purtroppo, riempie l'array errato, ripetendo lo stesso indice su un over.

Questo è il mio codice:

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

E data questa matrice:

[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]; 

restituisce:

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

io non riesco a capire dove l'errore logico sta succedendo. Qualcuno potrebbe aiutarmi a trovarlo?

Answer 1

Inizialmente compilare l'indx con i numeri da 0 a len -1 e utilizzare l'accesso indicizzato per la scansione e la manipolazione dell'array. Il tuo codice attuale ha il potenziale di andare fuori sincrono con l'input. E non hai bisogno del tempData.

quindi qualcosa di simile:

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

C'è un problema con il vostro algoritmo. Dì che il valore minimo è nell'ultima posizione. Memorizzi l'ultima posizione al primo posto dell'indice dell'array. Quindi si scambia il valore con il valore nella prima posizione. Quindi ora la tua ultima posizione potrebbe contenere il minimo dei valori rimanenti.

Inizializza invece l'array di indici con {0,1,2,3,4,5,6 ...} quindi ordina quell'array in base ai valori dei dati in tali indici.

Answer 3

il problema è che non dovresti scambiare il contenuto dell'array per ottenere l'ordine giusto, basta "contrassegnarlo" (potresti vedere la risposta di Hal sulla spiegazione dell'errore). ciò dovrebbe generare il giusto:

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

L'array memorizza indice l'indice dell'ultima posizione durante il processo di sequenziazione, anziché l'indice originale.

Così inizializzare l'array indice con l'indice originale

indx[i] = i; 

operazioni di permuta dei dell'indice durante il processo di ordinamento

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

Answer 5

qui è l'errore di logica. Ogni volta che un elemento viene selezionato per l'elaborazione e richiede un movimento dalla sua posizione, l'indice dell'elemento cambia pure per esempio, dopo aver elaborato il primo elemento (8.5) all'indice 0, viene spostato all'indice del l'elemento più piccolo nell'indice 12 e così via. la soluzione che comporta l'uso di "bandiere" sembra appropriato