BubbleSort Vector

Question

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

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() - это атрибут для сортировки объектов.

Answer 1

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

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>.
• Эта вещь как третий параметр функции называется «lambda». Lambdas - это в основном функции без имен, которые вы можете просто написать в середине своего кода и пройти. Я предлагаю вам ознакомиться с ними, поскольку они являются важной концепцией в области программирования и программирования (независимо от используемого вами языка).
• Поскольку вы хотите, чтобы элементы, отсортированные по убыванию, были релевантны и std::sort сортируют по возрастанию (?) По умолчанию, лямбда возвращается true, если значение b составляет менее a.
• Использование стандартного алгоритма сортировки, в дополнение к тому, чтобы быть короче и слаще, чем ваш ручной код, и намного более вероятно, будет правильным, означает, что вы получаете очень хорошую производительность в целом (как алгоритмическая производительность Big-O и реализация - (в общем случае.)