Bubble sort on a multi dimensional array

Projects Programming
1

OK so… new here so please be gentle…..

I’m manipulating data in arrays…
Base data array =
String ukRepeaters[72][11] = { {"CALL" , "CH" , "Tx" , "Rx" , "MH" , "Loc" "Area" , "CTCSS", "Owner", "Lat" , "Lon" },
{"GB3SN","RV58","145.7250","145.1250","IO91LC","ALTON HANTS", "SW", "71.9", "G4EPX", "51.083333", "1.083333"},
{"GB3AL","RV59","145.7375","145.1375","IO91QP","AMERSHAM", "SW", "77", "G0RDI", "51.625000", "0.666666"},
….. etc.

I use this data to calculate the distance away for my current location and store the results into another array….

double repeaterDistances [72][9];
// index [0]
// lat [1] // converted to float
// lon [2] // converted to float
// latRadians [3] // repeater lat in radians
// lonRadians [4] // repeater lon in radians
// distanceToRepeaterFromCurrentLocation [5]
// bearingToRepeater [6]

All OK so far….

The data in ‘repeaterDistances’ is then used to calculate the distance and bearing and store the results in same array….

All OK so far….

I now want to sort the repeaterDistances array by distance and store the results into a third array
double sortedRepeaters[72][3];
// index [0]
// distance [1]
// bearing [2]

This is my problem… I’ve spent a couple of days now going around in circles getting myself completely confused with the sort algorithm and save routine, any suggestions welcome …
My sort routine starts at line 200, hardware is a Teensy 3.2 so no problems with floating point cals etc. The calculations are all working it now just data manipulation within arrays.

Thanks for looking.

Repeater_Sort_Test_4.ino (18 KB)

2

I'm manipulating data in arrays…

...but not code tags

3

This array:

   // lat                                 [1] // converted to float
   // lon                                [2] // converted to float
   // latRadians                     [3] // repeater lat in radians
   // lonRadians                     [4] // repeater lon in radians
   // distanceToRepeaterFromCurrentLocation  [5]
   // bearingToRepeater           [6]

Already has the distance and bearing information.

Can you save memory by creating an array of bytes which act as pointers or indexes to elements of the above array? You go through that array and find the smallest distance value; the index to that element is stored in the new array's [0] element. Then find the next largest and store its index into [1] and so on.

When you want to index into the distance array in order, get the actual index from this new array.

4

Thanks 'Blackfin' that makes a lot of sence, a byte array should do it... I'll give it a go...
I think I just needed a stear in the right direction :slight_smile:

5

Would you be better off using arrays of structures instead of multidimensional arrays? That way you could at least reference members by name.

double repeaterDistances              [72][9];
// index                                  [0]
// lat                                    [1] // converted to float
// lon                                    [2] // converted to float
// latRadians                             [3] // repeater lat in radians
// lonRadians                             [4] // repeater lon in radians
// distanceToRepeaterFromCurrentLocation  [5]
// bearingToRepeater                      [6]

typedef struct {
  double index;
  double lat;
  double lon;
  double latRadians;
  double lonRadians;
  double distanceToRepeaterFromCurrentLocation;
  double bearingToRepeaterl;
} rd;

rd repeaters[72];
6

I now want to sort the repeaterDistances array by distance and store the results into a third array

I'm pretty sure that a bubble sort is an "in-place" sort - you can't just put the results into a third array, because the whole algorithm relies on having all of the data in the arry you are looking at. (You can copy the whole array into your third array, and then sort it in-place...)

         if((repeaterDistances[j][5]) > (repeaterDistances[j][5]+1));

int t = repeaterDistances[j][5];

I think you are doing the +1 in the wrong place. Should be "j+1" inside the first array index?

Most in-place sort algorithms are based on "compare" and "swap" operations, and your code will be a lot more obvious looking if you write functions that abstract those operations:

   if (isLarger(j, j+1) {
      swap(j, j+1);
   }

// :
void swap(int index1, int index2) {
   // swap keys
   // swap other data
   // etc
}