sorting a 2 dimensional array

Well, the clue here is that it really is a 1 dimensional array you want to sort. Each element is an array but that's immaterial:

std::sort() can be used, but you should supply your own comparer. It all depends on what the data structure is exactly. the natural way would be to have one array of struct or some such:

struct entry {
   double val;
   int another_val;
};

and the array is an array of such elements.

Then you can easily avoid the comparer also, just define your own < operator for struct entry:

bool operator < (const entry & a, const entry & b)
{ return a.val < b.val; }

Then if you have an array of n elements of entry:

void sort(const entry arr[], int n)
{
   std::sort(arr,arr + n);
}

would then sort the array.

if you have the structure as two separate arrays:

double val[];
int another_val[];

Then you need to do it slightly differently, however, this is such a silly way to organize those data that unless you confirm you have done it this way I won't bother to show how to sort them in this situation.

Alf

as it stands the array is defined as two dimensional -

float array[2][10]; //say.

i'd rather not re-write as an array of structs if poss.

i;m happy to do a compare fn, but the sort template confuses me as i don;t know how to use it - hence begging for a worked example!

When the sort algorithm determines that it needs to swap two elements (or move an element) swap (or move) the items in both columns of the array.  The rest of the sort is unaffected.


Kdo

i;m really suffering with this!!

i have tried salte's suggestion to use a single array of structs as above, which is fine but i get an error requiring an overload of the = operator, which i can't get right. Salte - any help on this?

Kdo - can you provide an example please?

thanks evryone

Do you know how to do any normal on dimensional array sorts??  If you want the quick and dirty way to do it just use one of them, like a bubble-sort and everytime you move on of the elements in the first column then move the elements in the second column.

void Bubble_Sort (double array[][], int num_elem)
{
     int swap, temp, temp2;
     do
     {
          swap = 0;
          for(int count = 0; count<(num_elem-1); count++)
          {
                 if(array[count][0] > array[count+1][0])
                 {
                         temp = array[count][0];
                         temp2 = array[count][1];
                         array[count][0] = array[count+1][0];
                         array[count][1] = array[count+1][1];
                         array[count+1][0] = temp;
                         array[count+1][1] = temp2;
                         swap = 1;
                 }
          }
     }(while(swap != 0);
}


This is a Bubble Sort found in many books, I just modified it a little to account for two columns.

to intern: yes, i do, and it;s prohibitively slow for what i want to do. but thanks.

no prob.  Just thought I would trow my $.02 in.

How many elements are you talking about sorting ?  thousands??

to intern: hundreds of thousands.

anyone understand operator= overload in structs?

i;ve declared it as a unary operator in the struct def but no joy ...

Ok, here is one way to do it, both values are float....so..

Clue: The sort function in stl require two things to work:

An iterator that can iterate through all elements in the 'array'. The iterator must be a random iterator that can move around as it please.

A compare function to compare two values that the iterator returns. If you have two iterators a and b then *a return the element at a and *b return the element at b and *a < *b must be defined. Now, we want the iterator to return the array of two elemenents so we can't use the double array directly, instead we make the iterator be an iterator that return a struct with two floats and that is a 'virtual array' in that std::sort will believe that the array is an array of that struct but in reality that array never exist and we use our original array.

To make this illusion work we define a class or struct:

struct entry {
   float a;
   float b;

   entry(float aa, float bb) : a(aa), b(bb) {}
};

We also want to create an iterator for the struct, this iterator must actually iterate over the real array and handle assignments etc to the struct, thus we make a class that is our iterator:

class entry_iterator {
private:
   ....
public:
   enum {
      n2 = 10, // number of elements in inner array.
   };
   entry_iterator(float arr[][n2]);

   shadow_entry & operator * ();
   entry_iterator & operator ++ ();

   // need this for random iterator
   entry_iterator & operator += (int k);

};

The shadow_entry is a class that holds a 'value' of the fake array. This value must reference the real array:

class shadow_entry {
private:
    float (*arr)[][entry_iterator::n2];
    int x; // index;

    friend class entry_iterator;

    shadow_entry(float a[][entry_iterator::n2], int xx)
     : arr(a), x(xx)
    {}

public:
    /* here we do our magic */
    shadow_entry & operator = (const shadow_entry & o)
    {
       arr[0][x] = o.arr[0][o.x];
       arr[1][x] = o.arr[1][o.x];
       return *this;
    }

    shadow_entry & operator = (const entry & o)
    {
       arr[0][x] = o.a;
       arr[1][x] = o.b;
    }

    bool operator < (const shadow_entry & o) const
    { return arr[0][x] < o.arr[0][o.x]; }

    operator entry () const
    { return entry(arr[0][x],arr[1][x]); }

    /* more magic */
    typedef entry value_type;
};

Now as entry_iterator return a shadow_entry you can do things like:

entry_iterator i;
entry_iterator j;

entry e = *i;

i += 5;

*j = *i;

Note that *j = *i will cause the entry pointed by j to be modified to be identical to the entry pointed at by i.

If you want to swap them you probably save to a temp first:

shadow_entry tmp = *i;
*i = *j;
*j = tmp;

oops. that code won't work very well, the reason is that tmp doesn't really save the values, it just remember where i references.

This means that the iterator must specify an entry as the value_type.

entry tmp = *i;
*i = *j;
*j = tmp;

will work beautifullly.

It is possible I have left out some things that is required for the iterator but this should more or less do it for you.

so std::sort(entry_iterator(arr,0), entry_iterator(arr,n1));

where n1 is the number of elements in the inner array should work.

This look a bit ugly but this is partly caused by a very silly datastructure to start with - and why the first index is the one that goes 0 and 1 and you want to sort the second index is part of the problem, why you didn't use struct is also part of the problem.

It is also partly caused by the requirement that we don't make an additional data structure and sort that structure instead.

It is also possible you might just want to sort the elements using bubble sort yourself. This will not use STL but because your structure is the way it is it doesn't really lend itself to STL very easily as indicated above.

void sort(float arr[2][10])
{
   for (int i = 10; i > 0; --i) {
      for (int j = 1; j < i; ++j) {
         if (arr[0][j-1] > arr[0][j]) {
            // swap arr[0][j-1] and arr[0][j]
            float a = arr[0][j-1];
            arr[0][j-1] = arr[0][j];
            arr[0][j] = a;
            // and arr[1][j-1] and arr[1][j]
            a = arr[1][j-1];
            arr[1][j-1] = arr[1][j];
            arr[1][j] = a;
         }
      }
   }
}

This code is actually shorter than the code using stl. Normally it would be the other way around. Also, be aware that this assume that the number of elements to sort is small (10 or so), if it is 20 or 2000 this function is definitely not what you want.

I really think you should consider changing your data structure, why is it stored in such a manner?

Alf

A bubble sort's pretty good -- especially for sorting native data types (int, fp) in memory.

Intern's given you the code.

Kdo

Overloading the = operator?

If you use a struct entry you shouldn't have to overload the = operator as one is provided. I.e. if you declare the structures as:

struct entry {
  float a;
  float b;
};

entry arr[10];

should be almost all that is needed. What you need is

bool operator < (const entry & a, const entry & b)
{ return a.a < b.a; }

Then

std::sort(arr,arr+10); should do it, you shouldn't need anything more than that.

If you want to keep your original array and then have a virtual array and sort the real array through iterators of the virtual array - you need to do more coding, but that largely comes because you want to do a lot of trickery.

If the array is a simple array of structs, then the above should be all that is needed well, you have to #include the files etc first.

Alf

thanks, especially to salte/alf for the very detailed explanation.

however, i have already taken on board salte's original suggestion to store the data as an array of structs. it seems more sensible.

so now i have :

struct thing
{
   float val;
   float another_val;
};

//then i define the array of things as follows:
thing* my_array; //this is because it is dynamically sized.

so when i use it:
my_array = new thing[the_number_of_elements];

i wish to sort it so i include <algorithm> and use

 
void sort(const thing array[], int n)
{
  std::sort(array,array + n);
}

//then
bool operator< (const thing &a, const thing &b)
{
   return (a.val<b.val);
}

HOWEVER - on compilation i get error C2678 binary"=" ... i enclose the exact compiler error below:
:\program files\microsoft visual studio\vc98\include\algorithm(584) : error C2678: binary '=' : no operator defined which takes a left-hand operand of type 'const struct thing' (or there is no acceptable conversion)
        c:\program files\microsoft visual studio\vc98\include\algorithm(548) : see reference to function template instantiation 'void __cdecl std::_Unguarded_insert(const struct thing [],struct thing)' being compiled
c:\program files\microsoft visual studio\vc98\include\algorithm(585) : error C2678: binary '=' : no operator defined which takes a left-hand operand of type 'const struct thing' (or there is no acceptable conversion)
        c:\program files\microsoft visual studio\vc98\include\algorithm(548) : see reference to function template instantiation 'void __cdecl std::_Unguarded_insert(const struct thing [],struct thing)' being compiled

any suggestions? i;m going nuts. i do appreciate all your help, i;m upping the points

Your problem is simply the use of the word 'const' in the function sort(const thing array[], int n).  STL is complaining that it doesn't know how to set an item in a const array equal to another -- which is exactly what const prevents it from doing!

Your problem is simply the use of the word 'const' in the function sort(const thing array[], int n).  STL is complaining that it doesn't know how to set an item in a const array equal to another -- which is exactly what const prevents it from doing!

I apologize for the duplicate -- bad use of the refresh button.

What I wanted to add was that you can do the sort with your original 2D array if you use the C qsort function from the stdlib and some trickery.

You would define your array like this:

float array[10][2];

as in ten items of two floats each
and a compare function like this

int compare_floats( const void *f1, const void *f2 ) {
    float *farr1 = (float *)f1;
    float *farr2 = (float *)f2;
    return farr1[0] - farr2[0]; // or use farr1[1] for other element...
}

then call qsort like:

qsort( array, 10, sizeof(float)*2, compare_floats );

ARGHH!! so STUPID!!! many, many thanks to everyone.

Calum

Part of the problem is that his array was

float [2][10];

That is two arrays of 10 elements each, instead of 10 arrays of 2 elements each.

You can still use qsort but not directly on the array. Instead you would make an array that would originally hold the indices of the elements 0..9 and then you would sort that array using the compare function:

int compare(int x, int y)
{   return array[0][x] - array[0][y]; }


void do_sort(float arr[2][10])
{
   int sort_array[10];
   for (int i = 0; i < 10; ++i)
      sort_array[i] = i;
   qsort(sort_array,10,compare);

/*

and then that array would be sorted so that the elements in array contained the sort sequence, if the sort array then were something like:

int sort_array[10] == { 0, 5, 7, 2, 3, 9, ... };

after sort, then it means that the first element should be first, the second element should be the element originally at location 5 etc... you would then have to move the elements in the original array around until you got it in that sequence. Easiest is probably to first place the elements in a temporary array and then memcpy it back to the original:

*/

   float other[2][10];

   for (int i = 0; i < 10; ++i) {
      other[0][i] = arr[0][sort_array[i]];
      other[1][i] = arr[1][sort_array[i]];
   }
   memcpy(& arr[0][0],& other[0][0], sizeof(arr));
}

Also tricky, it is best the way he already did it. Also, the way he did it is more intuitive, this method I just showed works but it far from intuitive. In a similar problem earlier I had a hard time explaining to a guy why such an index array solved his problem.

Alf