Я написал алгоритм сортировки слиянием, когда я передаю стандартный компоратор от меньшего к большему, все работает нормально, но если я пытаюсь передать компоратор left > right, т.е от большего к меньшему, алгоритм работает неправильно. Как это можно исправить?
#include <iostream>
#include <vector>
using namespace std;
template <typename T,typename Comparator = std::less<int>>
void mergeSort(T* arr, size_t start, size_t end, Comparator cmp = Comparator())
{
if (end - start < 2)
return;
if (end - start == 2)
{
if (cmp(arr[start + 1], arr[start]))
swap(arr[start], arr[start + 1]);
return;
}
mergeSort<T>(arr, start, start + (end - start) / 2);
mergeSort<T>(arr, start + (end - start) / 2, end);
size_t auxSize = end - start;
T* aux = new T[auxSize];
size_t b1 = start;
size_t e1 = start + (end - start) / 2;
size_t b2 = e1;
size_t auxCurrentIndex = 0;
while (auxCurrentIndex < end - start)
{
if (b1 >= e1 || (b2 < end && cmp(arr[b2], arr[b1])))
{
aux[auxCurrentIndex] = arr[b2];
++b2;
}
else
{
aux[auxCurrentIndex] = arr[b1];
++b1;
}
auxCurrentIndex++;
}
for (size_t i = start; i < end; ++i)
arr[i] = aux[i - start];
}
int main()
{
int a[10] = {5, 4, 0, 9, 6, -10, 10, 9, 3, -2};
mergeSort<int>(a, 0, 10, [](int a, int b){
return a <= b;
});
for (std::size_t i = 0; i < 10; i++){
std::cout << a[i] << ' ';
}
}
Во-первых, исправьте саму сортировку - добавьте компаратор в рекурсивные вызовы!
mergeSort<T>(arr, start, start + (end - start) / 2, cmp);
mergeSort<T>(arr, start + (end - start) / 2, end, cmp);
Во-вторых, долой вашу лямбда-функцию в первом вызове - она обеспечена компаратором по умолчанию.
Ну, а для обратной сортировки - укажите обратный компаратор:
mergeSort<int>(a, 0, 10);
for (std::size_t i = 0; i < 10; i++){
std::cout << a[i] << ' ';
}
cout << "\n\n";
mergeSort<int,std::greater<int>>(a, 0, 10);
for (std::size_t i = 0; i < 10; i++){
std::cout << a[i] << ' ';
}
Вот полный код: https://ideone.com/jAFQNw
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
есть двусвязный список, необходимо сделать для него шаблон, чтобы можно было взаимодействовать с разными типами данных, подскажите как правильно...
Есть код, в котором генерируются последовательности и помещаются в inputtxt
я вот только не давно узнал про заголовочный файл #include <bits / stdc ++H> и зачал искать информацию по этой библиотеке