Сортировка по возрастанию, C++, с векторами
Я пытаюсь сделать функцию сортировки для std::vector, но у меня проблема с отрицательным values. Я не хочу использовать функцию vector::sort.
Очередь - это вектор.
Мой вклад:
1, -2, -241, 332, 2667, -2667, 266217, 2667, 13, -22, -41, 2332
Выход :
266217, 2667, 2667, 2332, 332, 13, 1, -2. -241, -2667, -22, -41
В принципе все работает, а то по непонятным мне причинам вылетает.
Функция:
void PriorityQueue::Push(double value)
{
std::vector<double>::iterator pr;
if (Queue.empty())
{
Queue.push_back(value);
}
else if (!Queue.empty())
{
for (pr = Queue.begin(); pr != Queue.end(); pr++)
{
if (value > *pr || value == *pr)
{
Queue.insert(pr, value);
break;
}
else if (value < 0)
{
if (value > *pr || value == *pr)
{
Queue.insert(pr, value);
break;
}
else if (value < *pr)
{
Queue.push_back(value);
break;
}
}
}
}
}
Я думаю, будет проще, если вы сначала push_back в вектор, а затем реализуете и используете алгоритм сортировки, такой как сортировка слиянием, в несортированном контейнере. Кроме того, почему value > *pr || value == *pr, а не value >= *pr?
Почему вы говорите: if (value > *pr || value == *pr) вместо более удобочитаемого выражения: if (value >= *pr)
В чем причина того, что std::sort не используется?
Хотя я не понимаю ваш алгоритм сортировки в отношении отрицательных чисел, в вашем коде нет ничего, что могло бы вызвать сбой. Сбой, вероятно, происходит в коде, который вы нам еще не показали.
Если ваш ввод в порядке {5,4,3,2,1} и вы вызываете Push для каждого значения (по порядку), в очередь будет вставлен только 5. Вы понимаете почему?
Что особенного в отрицательных числах в очереди приоритетов, которые требуют особой обработки в алгоритме сортировки.
Вам разрешено использовать std::upper_bound?
Начальное число «12» загадочно (возможно, вы делаете что-то не так при выводе), но в остальном это так, как говорит ваш код: убывающие положительные значения, за которыми следуют отрицательные в том порядке, в котором они были добавлены.
Переписав условное выражение, вы проясните, что происходит: if (value >= *pr) { Queue.insert(pr, value); break; } else if (value < 0 && value < *pr) { Queue.push_back(value); break; }. Обратите внимание, что если первое значение неотрицательно, все отрицательные значения добавляются в конце.
Если я не буду рассматривать значения <0 отдельно, они исчезнут в программе ..
@Xuuuc - причина того, что отрицательные числа «исчезают», заключается в том, что у вас есть ошибка в вашей программе. Когда value меньше элемента less в списке, ваш код не вставит его. См. Мой ответ ниже для очень простого решения.
В заголовке вашего вопроса написано «сортировка по возрастанию». Но ваш желаемый результат и код на самом деле являются «сортировкой по убыванию».
Будет легко не использовать vector::sort, поскольку такого нет.
Ответы 2
В этом методе действительно сложно понять желаемый порядок. Но я попытаюсь. Ты используешь
Queue.insert(pr, value);
поэтому я предполагаю, что pr должно быть перед значением в случае, если value> = * pr. Это означает в порядке убывания от максимального до минимального.
Вы хотите по убыванию. Тогда вам нужна позиция, когда предыдущий был больше или равен, а текущий элемент меньше значения. Так что пропустите все, пока эта позиция не будет найдена, а затем вставьте.
void PriorityQueue::Push(double value) { std::vector<double>::iterator pr; if (Queue.empty()) { Queue.push_back(value); return; } for (pr = Queue.begin(); pr != Queue.end(); pr++) { if (value < *pr) continue; Queue.insert(pr,value); break; } }
А в порядке возрастания - пропустите все, пока сначала не станет больше, а затем вставьте:
void PriorityQueue::Push(double value) {
std::vector<double>::iterator pr;
if (Queue.empty()) {
Queue.push_back(value);
return;
}
for (pr = Queue.begin(); pr != Queue.end(); pr++) {
if (value >= *pr)
continue;
Queue.insert(pr,value);
break;
}
}
Вам не нужно проверять «if (value <0)» - я думаю, что на этом этапе была допущена ваша логическая ошибка. Также не нужно проверять
if (!Queue.empty())в else-заявлении после
if (Queue.empty())это слишком много проверок и может вызвать много ошибок ...
Когда я использую этот код, я теряю все отрицательные значения в программе. Их больше нет (это было в моей программе раньше, поэтому я использовал оператор "if (values <0)"
Я совершенно уверен, основываясь на намеках, которые вы дали в своих комментариях, это то, что вы хотите. Не нужно специально обрабатывать пустой список или отрицательные числа. И если value не вставляется в цикл for, предполагается, что он находится в конце.
void PriorityQueue::Push(double value)
{
bool inserted = false;
for (auto pr = Queue.begin(); pr != Queue.end(); pr++)
{
if (value >= *pr)
{
Queue.insert(pr, value);
inserted = true;
break;
}
}
if (inserted == false) // handle the case of inserting a number at the end
{
Queue.push_back(value);
}
}
Это будет надежно вставлять элементы в порядке убывания без особой необходимости обрабатывать отрицательные числа специальным образом.
Вы пробовали выполнить код с помощью отладчика?