Sorting a selection of an invalid array index

Question

I am writing a sort that, given an array of unordered elements, will populate the new array with indexes of the sorted elements. For instance,

[3, 2, 1] 

will return

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

Unfortunately, it fills the array incorrectly, repeating the same index on top.

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 not understand where the logical error occurs. Can someone help me find it?

Answer 1

Initially fill indx with numbers 0 to len -1 and use indexed access to scan and manage the array. Your current code may not sync with the input. And you do not need 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 that you don’t have to change the contents of the array in order to get the correct order, just “tick” it (you can see Hal's error response). this should lead to the correct exit:

  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

The problem is with your algorithm. Say the minimum value is in the last position. You save the last position in the first place of your array index. Then you change the value there with the value in the first position. So, now your last position may contain a minimum of remaining values.

Instead, initialize your index array with {0,1,2,3,4,5,6 ...} then sort this array based on the data values ​​in these 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 source index

 indx[i] = i; 

Also change the index during the sorting process

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

Answer 5

here is a logical mistake. Each time an element is selected for processing and it needs to be moved from its position, the element index also changes, for example, after processing the first element (8.5) with index 0, it moves to the index of the smallest element with index 12, etc. a solution that involves the use of "flags" seems appropriate