Pointer Manipulation Help

Question

Hi everyone, I am trying to build a function in C/c++ to sort an array and replace each value with its "score" or rank. It takes in a double pointer array to an array of ints, and sorts the double pointers based on the dereferenced value of the integers. I have tried quite a few times to make it work, but cant get it down. Once again, it must sort the double pointers based on the values they point to. This is what I have:

void SortArray( int ** pArray, int ArrayLength ) {

int i, j, flag = 1;    // set flag to 1 to begin initial pass
int * temp;             // holding variable orig with no *
for(i = 1; (i <= ArrayLength) && flag; i++)
{
 flag = 0;
    for (j=0; j < (ArrayLength -1); j++)
    {
  if (*pArray[j+1] > *pArray[j])      // ascending order simply changes to <
  { 
                temp = &pArray[j];             // swap elements
                pArray[j] = &pArray[j+1];
                pArray[j+1] = &temp;
                flag = 1;               // indicates that a swap occurred.
           }
      }
 }
 };

thanks in advance.

Answer 1

You're close. You're referencing the address of the array items when you swap, which isn't necessary. The items in the array are pointers, and that's what needs to be swapped.

See below:

void SortArray( int ** pArray, int ArrayLength )
{
    int i, j, flag = 1;    // set flag to 1 to begin initial pass
    int * temp;             // holding variable orig with no *
    for(i = ArrayLength - 1; i > 0 && flag; i--)
    {
        flag = 0;
        for (j = 0; j < i; j++)
        {
            if (*pArray[j] > *pArray[j+1])      // ascending order simply changes to <
            { 
                temp = pArray[j];             // swap elements
                pArray[j] = pArray[j+1];
                pArray[j+1] = temp;
                flag = 1;               // indicates that a swap occurred.
            }
        }
    }
}

Also, check out this lovely blog post on Bubble Sorting in case you're interested (sorry, shameless plug :)). Hope that helps you with your homework ;)

---

Edit: Note the subtle "optimisation" where you count back from the array length and only increment up until 'i' in the inner loop. This saves you from needlessly reparsing items that have already been sorted.

Answer 2

Thanks!
Heh, this isnt homework. Its a genetic algorithm side project, and I think I will eventually be switching to a better sort algorithm, possibly shell, but have to get the basics first :p

Answer 3

Heh, this isnt homework.

If thats the case then consider using the STL to manage arrays and sort. Its easier to develop and maintain and the std::sort algorithm is asymptotically faster than bubble sort.

Answer 4

Hmm, I don't have much experience with the STL. Could you give an example? Thanks

P.S. - I don't have a whole lot of experience with life either :p

Answer 5

You should consider using std::swap() to do your swapping.

If you do, call it as such:

swap( obj1, obj2 );

rather than:

std::swap( obj1, obj2 );

As the first calling semantic will allow the proper name space look up to find the correct overload if one exists.

Be sure in have either:

using namespace std;

or:

using std::swap;

some where.

Answer 6

To complete Brian Ensink's post, you'll find the STL full of surprises. For example, the std::sort algorithm:

#include <iostream>
#include <vector>
#include <algorithm>

void printArray(const std::vector<int *> & p_aInt)
{
   for(std::vector<int *>::size_type i = 0, iMax = p_aInt.size(); i < iMax; ++i)
   {
      std::cout << "i[" << static_cast<int>(i) << "] = " << reinterpret_cast<unsigned     int>(p_aInt[i]) << std::endl ;
   }

   std::cout << std::endl ;
}


int main(int argc, char **argv)
{
   int a = 1 ;
   int b = 2 ;
   int c = 3 ;
   int d = 4 ;
   int e = 5 ;

   std::vector<int *> aInt ;

   // We fill the vector with variables in an unordered way
   aInt.push_back(&c) ;
   aInt.push_back(&b) ;
   aInt.push_back(&e) ;
   aInt.push_back(&d) ;
   aInt.push_back(&a) ;

   printArray(aInt) ; // We see the addresses are NOT ordered
   std::sort(aInt.begin(), aInt.end()) ; // DO THE SORTING
   printArray(aInt) ; // We see the addresses are ORDERED

   return EXIT_SUCCESS;
}

The first printing of the array will show unordered addresses. The second, after the sort, will show ordered adresses. On my compiler, we have:

i[0] = 3216087168
i[1] = 3216087172
i[2] = 3216087160
i[3] = 3216087164
i[4] = 3216087176

i[0] = 3216087160
i[1] = 3216087164
i[2] = 3216087168
i[3] = 3216087172
i[4] = 3216087176

Give STL's <algorithm> header a look http://www.cplusplus.com/reference/algorithm/ You'll find a lot of utilities. Note that you have other implementation of containers that could suit you better (std::list? std::map?).