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

Question

У меня есть массив структур, где я отслеживаю, сколько раз каждое уникальное слово было видно в данном тексте:

struct List {
  char word[20];
  int repeat;
};

Теперь мне нужно отсортировать это:

as             6
a              1
appetite       1
angry          1
are            2
and            4
...

На это:

a            1
as           6
and          4
are          2
angry        1
appetite     1
...

(Под алфавитом я подразумеваю только первую букву) До сих пор я придумал следующее:

for (i = 0; i < length - 1; i++) {
        min_pos = i;
        for (j = i + 1; j < length; j++) // find min
            if (array[j].word[0] < array[min_pos].word[0]) {
                min_pos = j;
            }
            swap = array[min_pos]; // swap
            array[min_pos] = array[i];
            array[i] = swap;
        }

Этот код отлично работает для сортировки по алфавиту, но я просто не могу написать правильный код для сортировки ОБА по алфавиту и по длине.

Answer 1

Другие отметили, что существуют более быстрые и чистые способы сортировки.Но если вы хотите использовать собственную сортировку выбора, как вы написали, тогда вам просто нужно внести несколько изменений в ваш код.

Отделите логику «мне нужно поменять местами» от логики свопингасам.Тогда код становится намного чище, и становится более понятно, куда добавить дополнительную проверку.

Я только скопировал здесь внутренний цикл.Вы хотите заменить существующий внутренний цикл на этот.Я не понимаю, зачем вам нужны swap_pos и min_pos, поэтому я оставил семантику в покое.

    for (j = i + 1; j < length; j++) { // find min
        // first, determine whether you need to swap
        // You want to swap if the first character of the new word is
        // smaller, or if the letters are equal and the length is smaller.
        bool doSwap = false;
        if (array[j].word[0] < array[min_pos].word[0]) {
            doSwap = true;
        }
        else if (array[j].word[0] == array[min_pos].word[0] &&
                 strlen(array[j].word) < array[min_pos].word) {
            doSwap = true;
        }

        // do the swap if necessary
        if (doSwap) {
            swap_pos = j;
            swap = array[min_pos]; // swap
            array[min_pos] = array[i];
            array[i] = swap;
        }
    }

Чтобы более наглядно проиллюстрировать необходимые логические изменения, я намеренно избегал делатьзначительные изменения стиля или простая оптимизация.

Answer 2

Использование лексикографических операторов сравнения кортежей

Простой способ не записать это условие -

#include <tuple>

Тогда std::tie можетбыть использованы:

std::tie(array[j].word[0], array[j].repeat) < std::tie(array[min_pos].word[0], array[min_pos].repeat)

Это работает, потому что std::tie создает кортеж lvalue ссылок на свои аргументы.(Это означает, что std::tie требует переменных. Если вы хотите сравнить результаты с функциями std::make_tuple или std::forward_as_tuple, будет лучше)

И std::tupleимеет операторов , которые

Лексикографически сравнивает lhs и rhs, то есть сравнивает первые элементы, если они эквивалентны, сравнивает вторые элементы, если они эквивалентны, сравнивает третийэлементы и так далее.

И приведенное выше описание также является идеей, как сделать сравнение больше, чем значение.

Answer 3

Вы можете передать лямбду на sort, чтобы сделать это:

sort(begin(array), end(array), [](const auto& lhs, const auto& rhs){ return *lhs.word < *rhs.word || *lhs.word == *rhs.word && (strlen(lhs.word) < strlen(rhs.word) || strlen(lhs.word) == strlen(rhs.word) && strcmp(lhs.word, rhs.word) < 0); });

Live Example

Answer 4

Создайте функцию сравнения .

Добавьте operator< к вашему List:

bool operator<(const List &lhs) const {
    if(word[0] != lhs.word[0]) {
        return word[0] < lhs.word[0];
    }
    return strlen(word) < strlen(lhs.word);
}

И теперь используйте этот оператор для сортировки, используя любоеАлгоритм поражает ваше воображение.