Sortowanie przy pobieraniu błędnego indeksu tablicy

Question

Piszę sortowanie selekcji, które, biorąc pod uwagę tablicę nieuporządkowanych elementów, wypełni nową tablicę indeksami posortowanych elementów. Na przykład,

[3, 2, 1] 

powróci

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

Niestety wypełnia układ nieprawidłowo, powtarzając ten sam indeks nad drugą.

To jest mój kod:

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

A biorąc pod uwagę to tablica:

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

zwraca:

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

I nie może wydawać się dowiedzieć gdzie błąd logiczny występuje. Czy ktoś mógłby mi pomóc go znaleźć?

Answer 1

Początkowo zapełnij indx numerami od 0 do len -1 i użyj dostępu indeksowanego do skanowania i manipulowania tablicą. Twój obecny kod może się zsynchronizować z danymi wejściowymi. I nie potrzebujesz tempData.

więc coś takiego:

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

Jest problem z algorytmem. Powiedzmy, że minimalna wartość znajduje się w ostatniej pozycji. Przechowujesz ostatnią pozycję na pierwszym miejscu indeksu tablicy. Następnie zamieniasz tam wartość z wartością na pierwszej pozycji. Teraz Twoja ostatnia pozycja może zawierać minimalne pozostałe wartości.

Zamiast tego zainicjuj tablicę indeksów za pomocą {0,1,2,3,4,5,6 ...} , a następnie posortuj tę tablicę na podstawie wartości danych w tych indeksach.

Answer 3

Problem polega na tym, że nie powinieneś zamieniać zawartości tablicy, aby uzyskać prawidłową kolejność, po prostu "oznacz ją" (możesz zobaczyć odpowiedź Hala na wyjaśnienie błędu). ten powinien produkować odpowiednią moc:

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

indeksu tablicy przechowuje indeks ostatniej pozycji w procesie sortowania, zamiast oryginalnego indeksu.

więc zainicjować tablicę indeksu z oryginalnego indeksu

indx[i] = i; 

zamiana także indeks podczas procesu sortowania

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

Answer 5

tu jest błąd logiczny. Za każdym razem, gdy element jest wybrany do przetwarzania i wymaga przesunięcia z jego położenia, indeks elementu zmienia się na przykład , na przykład, po przetworzeniu pierwszego elementu (8.5) w indeksie 0, zostaje przeniesiony do indeksu najmniejszy element w indeksie 12 i tak dalej. Rozwiązanie, które wymaga użycia "flag" wydaje się odpowiednie