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?

I'm curious as to why people are downvoting this. It's a well defined question. — m0meni
– m0meni, Commented Feb 23, 2016 at 4:52

perreal · Accepted Answer · 2016-02-23 05:58:25Z

4

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

edited Feb 23, 2016 at 5:58

answered Feb 23, 2016 at 4:59

perreal

98.7k23 gold badges159 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user1883368 Over a year ago

Could you please provide a code sample? I tried to implement what you said but I'm still having difficulty getting it to work.

malioboro · Accepted Answer · 2016-02-23 05:10:46Z

4

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

edited Feb 23, 2016 at 5:10

answered Feb 23, 2016 at 5:03

malioboro

3,3514 gold badges38 silver badges57 bronze badges

Comments

Hal · Accepted Answer · 2016-02-23 05:01:02Z

2

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.

answered Feb 23, 2016 at 5:01

Hal

1,1399 silver badges20 bronze badges

Comments

ydoow · Accepted Answer · 2016-02-23 05:05:40Z

1

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;

answered Feb 23, 2016 at 5:05

ydoow

2,9964 gold badges27 silver badges42 bronze badges

Comments

Spyke · Accepted Answer · 2016-02-23 05:40:47Z

1

here is the logic error. Each time an element is selected for processing, and it requires movement from its position, the index of the element changes as well for example, after processing the first element (8.5) at index 0, it gets moved to the index of the smallest element at index 12 and so on. the solution that involves the use of "flags" seem appropriate

answered Feb 23, 2016 at 5:40

Spyke

1344 bronze badges

Collectives™ on Stack Overflow

Selection sort fetching wrong index of array

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related