c++, sort a struct by last then first name

Question

I have the algorithm for sort by last name, but I am having trouble figuring out how to sort by last name, then if two people have the same last name, sort by their first name.

void sortLastName(FRIEND friends[ARRAY_MAX], int& count) {

    FRIEND temp;

    for(int i = 0; i < count - 1; i++) {
     for (int j = i + 1; j < count; j++) {
      if (stricmp(friends[i].lastName, friends[j].lastName) > 0)  {
       temp = friends[i];    //swapping entire struct
       friends[i] = friends[j];
       friends[j] = temp;
      }
     }
    }
}

=== EDIT ====================

I don't want to use STD sort()

Answer 1

First, compare the last names. If they are equal, then compare the first names:

int compareResult = stricmp(friends[i].lastName, friends[j].lastName);
if(compareResult == 0)
    compareResult = stricmp(friends[i].firstName, friends[j].firstName);
if(compareResult < 0)
    // swap friends[i] and friends[j]

Answer 2

Firstly, use qsort or the proper C++ equivalent which takes a function which compares two objects.

The comparison should then be trivial:

int compare_by_name(const FRIEND& f1, const FRIEND& f2)
{
    int last_name_matches = strcmpi(f1.lastName, f2.lastName);
    return (last_name_matches != 0) ? last_name_matches :
            strcmpi(f1.firstName, f2.firstName) ;
}

NB: a real C++ implementation would probably use templates for the comparator function.

Answer 3

Add the following:

else if (stricmp(friends[i].lastName, friends[j].lastName) == 0 &&
         stricmp(friends[i].firstName, friends[j].firstName) > 0) {
    temp = friends[i];    //swapping entire struct
    friends[i] = friends[j];
    friends[j] = temp;
}

Answer 4

You have to change your comparison. The basic algorithm is if friends[i] > friends[j] then swap them. So change your definition of ">" to include first name comparisons.

Something like the following ought to do:

if (stricmp(friends[i].lastName, friends[j].lastName) > 0 ||
    (stricmp(friends[i].lastName, friends[j].lastName) == 0 && 
    stricmp(friends[i].firstName, friends[j].firstName) > 0))

You might want to do the last name comparison only once though (store it in a temp variable instead of comparing twice), but the idea is the same.

Note that the "best" way to do this might be to provide comparison functions in the FRIEND class. Then you can use if(friends[i].CompareTo(friends[j]) > 0) instead.

Answer 5

Please don't implement sorts by yourself - std::sort (in <algorithm>) does this job much better and much more efficient. (Except you just want to see how your algorithm works for experimental purpose)

You will have to specify a comparison function or better a functor anyway.

struct FriendComparer {
  bool operator () (const FRIEND& a, const FRIEND& b) {
      // Comparison code here (see previous posts)
  }
};

You can just invoke it like this:

std::sort(friendArray, friendArray + count, FriendComparer());

Answer 6

Why aren't you using std::sort? That's what it's for:

struct NameComparer {
  bool operator()(const FRIEND& lhs, const FRIEND& rhs){
    int compareResult = stricmp(lhs.lastName, rhs.lastName);
    if(compareResult == 0){
      compareResult = stricmp(lhs.firstName, rhs.firstName);
    }
    return compareResult < 0;
  }
};

std::sort(friends, friends + ARRAY_MAX, NameComparer());

Of course, you really should use the C++ std::string class as well. That's what it's for. And then you don't have to screw around with error-prone C string manipulation functions like stricmp.

Answer 7

In addition to the choice of building a comparison function that uses both names, you can sort on the fist names then sort on the last names, but you must take care to use a stable sort for the second pass. Might as well use it for the first too.

Good news: std::stable_sort is available and guaranteed to be, well, stable (thanks to Adam and libt for the correction). The plain std::sort and the c standard library qsort are not guaranteed to be stable, though some implementation might be. As Mark points out in the comments, the bubble sort you exhibit is already stable.

---

This is less efficient that the single-sort-with-a-custom-compare-function choice, but it makes it easy to let you user select multiple sorts at run-time (because you don't have to define every possible comparison function, or a mini-language).

Answer 8

Define a comparison function (or class as jalf suggested) and use the STL's std::sort():

bool compareFriends(FRIEND const & lhs, FRIEND const & rhs)
{
    int const resultLast = stricmp(lhs.lastName, rhs.lastName);

    if(resultLast == 0)
    {
        return stricmp(lhs.firstName, rhs.firstName) < 0;
    }
    else
    {
        return resultLast < 0
    }
}

void sortLastName(FRIEND friends[ARRAY_MAX], int& count)
{
    std::sort(friends, friends + count, &compareFriends);
}

Answer 9

If you don't mind using boost.tuple (and replacing or at least modifying your existing implementation of Friend), there is an included comparison function.

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

typedef boost::tuple<std::string, std::string> Friend;

Friend f1, f2;
bool compareFriends = f1 < f2;

All the above should work.

Answer 10

you can use a concatenation of left aligned last name and first name as a sorting key

this is another point of view you're looking for, i think :)

string key(const FRIEND& aFriend)
{
    const int INITIALS_MAX_LENGTH = 200; // assume the worst

    string firstNameKeyPart = string(INITIALS_MAX_LENGTH, ' ');
    string lastNameKeyPart = string(INITIALS_MAX_LENGTH, ' ');

    firstNameKeyPart.replace(0, 0, aFriend.firstName);
    lastNameKeyPart.replace(0, 0, aFriend.lastName);

    return  lastNameKeyPart + firstNameKeyPart;
}

//...

if ( key(friends[i]) > key(friends[j]) )
{
  //swap
}