BubbleSort Vector

Question

BubbleSort Vector

Я пытаюсь отсортировать вектор объектов на основе одного из атрибутов объектов. Каждый объект имеет целочисленное значение, связанное с ним. Я пытаюсь использовать сортировку пузырьков для сортировки массива по убыванию, но, похоже, он ничего не делает. Вот что я попробовал:

void Database::sort (vector<Play*> &vec) {
for (int i = 0; i < (vec.size() - 1); i++) {
if (vec.at(i)->getRelevance() < vec.at((i + 1))->getRelevance()) {
Play *tempObj = new Play(vec.at(i));
vec.at(i) = vec.at((i +1));
vec.at((i + 1)) = tempObj;
}
}
}

getRelevance () — это атрибут для сортировки объектов.

1

bubble-sort c++vector

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Одна из проблем с вашим кодом состоит в том, что он содержит только один цикл! Если вы хотите сделать пузырьковую сортировку, вам нужно две вложенные циклы. Например, это, вероятно, будет работать:

void Database::sort (vector<Play*> &vec) {
bool have_swapped = true;
for (unsigned j = 1; have_swapped && j < vec.size(); ++j) {
have_swapped = false;
for (unsigned i = 0; i < vec.size() - j; ++i) {
if (vec[i]->getRelevance() < vec[i + 1]->getRelevance()) {
have_swapped = true;
Play * tempObj = vec[i];  // Just use:
vec[i] = vec[i + 1];      //    std::swap(vec[i], vec[i + 1]);
vec[i + 1] = tempObj;     // instead of these three lines.
}
}
}
}

Вы видите внешнюю петлю? У этого есть два использования. Во-первых, это фактически гарантирует, что мы прочесываем вектор, в то время как все еще есть элементы не в порядке (называется инверсий в учебниках по алгоритму, я полагаю,) и во-вторых, это не позволяет нам проходить и бессмысленно проверять элементы, которые «всплыли» до конца вектора в результате предыдущих итераций внутреннего цикла.

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

std::sort (vec.begin(), vec.end(),
[](Play * a, Play * b){return b->getRelevance() < a->getRelevance();}
);

И это в значительной степени так.

Некоторые заметки:

Вы должны включить <algorithm>,
Эта вещь, как третий параметр функции называется «лямбда«. Лямбды — это, по сути, функции без имен, которые вы можете просто написать в середине своего кода и передать. Я предлагаю вам ознакомиться с ними, поскольку они являются важной концепцией в вычислениях и программировании (независимо от языка, который вы используете.)
Поскольку вы хотите, чтобы элементы сортировались в порядке убывания релевантности и std::sort сортируется по возрастанию (?) по умолчанию, лямбда возвращает true, когда bуместность меньше чем a«S.
Использование стандартного алгоритма сортировки, в дополнение к тому, что он короче и слаще, чем ваш свернутый вручную код, и с гораздо большей вероятностью будет правильным, означает, что вы в целом получаете очень хорошую производительность (как алгоритмическую производительность Big-O, так и реализацию). Конечно, это будет намного лучше, чем пузырьковая сортировка (в общем случае.)

3