Сортировать структуру по фамилии и имени

Question

У меня есть алгоритм сортировки по фамилии, но у меня возникают проблемы с выяснением, как сортировать по фамилии, тогда, если два человека имеют одинаковую фамилию, сортируйте по имени.

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;
            }
        }
    }
}

=== РЕДАКТИРОВАТЬ ====================

Я не хочу использовать STD sort()

Answer 1

Почему вы не используете std::sort? Вот для чего:

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());

Конечно, вы действительно должны использовать класс C ++ std::string. Вот для чего это. И тогда вам не придется облажаться с ошибочными функциями C-строки, такими как stricmp.

Answer 2

Сначала сравните фамилии. Если они равны, то сравните имена:

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 3

Во-первых, используйте qsort или соответствующий эквивалент C ++, который принимает функцию, которая сравнивает два объекта.

Сравнение должно быть тривиальным:

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) ;
}

Примечание: реальная реализация C ++, вероятно, будет использовать шаблоны для функции компаратора.

Answer 4

Вы должны изменить свое сравнение. Основной алгоритм заключается в том, что если друзья [i]> друзья [j], то меняйте их местами. Поэтому измените определение «>», чтобы включить сравнения имен.

Что-то вроде следующего должно сделать:

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))

Возможно, вы захотите выполнить сравнение фамилии только один раз (сохраните его во временной переменной вместо сравнения дважды), но идея та же.

Обратите внимание, что «лучший» способ сделать это - предоставить функции сравнения в классе FRIEND. Тогда вы можете использовать if(friends[i].CompareTo(friends[j]) > 0) вместо.

Answer 5

В дополнение к выбору построения функции сравнения, которая использует оба имени, вы можете сортировать по первым именам , а затем сортировать по фамилиям, но вы должны позаботиться об использовании стабильный сортировка для второго прохода. Можно также использовать его для первого.

Хорошие новости: std::stable_sort доступно и гарантированно будет стабильно (спасибо Адаму и Либту за исправление). Обычная std::sort и стандартная библиотека c qsort не гарантируются стабильными, хотя некоторые реализации могут быть. Как отмечает Марк в комментариях, вид пузыря, который вы демонстрируете, уже стабилен.

---

Это менее эффективно, чем выбор единственной сортировки с настраиваемой функцией сравнения, но позволяет легко выбирать несколько сортировок во время выполнения (поскольку вам не нужно определять каждый возможная функция сравнения или мини-язык).

Answer 6

Если вы не возражаете против использования boost.tuple (и замены или, по крайней мере, изменения существующей реализации Friend), есть встроенная функция сравнения.

#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;

Все вышеперечисленное должно работать.

Answer 7

Пожалуйста, не выполняйте сортировку самостоятельно - std :: sort (в <algorithm>) делает эту работу намного лучше и намного эффективнее. (За исключением того, что вы просто хотите увидеть, как работает ваш алгоритм для экспериментальных целей)

Вы все равно должны будете указать функцию сравнения или лучше функтор.

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

Вы можете просто вызвать его так:

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

Answer 8

Вы можете сортировать по фамилии, и если фамилии совпадают, сортируйте их по именам. Примерно так (используется Bubble sort):

for (int i = 1; i < dictionary.size(); ++i)
    for (int j = 0; j < dictionary.size()-1; ++j) {
        if (dictionary[i].Last < dictionary[j].Last)
            swap(dictionary[i], dictionary[j]);
    }

for (int i = 1; i < dictionary.size(); ++i)
    for (int j = 0; j < dictionary.size() - 1; ++j) {
        if (dictionary[i].Last == dictionary[j].Last && dictionary[i].First < dictionary[j].First)
            swap(dictionary[i], dictionary[j]);
    }

Answer 9

вы можете использовать объединение выровненных по левому краю фамилии и имени как ключа сортировки

это еще одна точка зрения, которую вы ищете, я думаю:)

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
}

Answer 10

Определите функцию сравнения (или класс, как предложил jalf) и используйте 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);
}