Selection sort fetching wrong index of array

Question

I'm writing a selection sort that, given an array of unordered elements, will fill a new array with the indexes of the sorted elements. For example,

[3, 2, 1]

would return

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

Unfortunately, it fills the array incorrectly, repeating the same index over an over.

This is my 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;
  }
}

And given this 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];

it returns:

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

I can't seem to figure out where the logic error is occurring. Could someone help me find it?

Answer 1

Initially populate the indx with numbers 0 to len -1, and use indexed access for scanning and manipulating the array. Your current code has the potential to go out of sync with the input. And you don't need the tempData.

so something like this:

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

the problem is you shouldn't swap the content of the array to get the right order, just "flag" it (you could see Hal's answer about the error explanation). this should produce the right output:

  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 3

There's a problem with your algorithm. Say the minimum value is in the last position. You store the last position in the first place of your array index. Then you swap the value there with the value in the first position. So now your last position could well contain the minimum of the remaining values.

Instead initialise your array of indexes with {0,1,2,3,4,5,6 ...} then sort that array based on the values of the data at those indexes.

Answer 4

The index array stores the index of the last position during the sorting process, instead of the original index.

So initialize the index array with the original index

indx[i] = i;

Also swap the index during your sorting process

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