Как можно переписать алгоритм сортировки слиянием, чтоб он поддерживал сортировку от большего к меньшему исходя из переданного из вне компоратора

234
21 апреля 2022, 17:30

Я написал алгоритм сортировки слиянием, когда я передаю стандартный компоратор от меньшего к большему, все работает нормально, но если я пытаюсь передать компоратор 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] << ' ';
    }
}
Answer 1

Во-первых, исправьте саму сортировку - добавьте компаратор в рекурсивные вызовы!

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

READ ALSO
Шаблон списка c++

Шаблон списка c++

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

79
Удаление элементов в файле

Удаление элементов в файле

Есть код, в котором генерируются последовательности и помещаются в inputtxt

180
Стоит ли когда либо использовать #include &lt;bits / stdc ++.h&gt;?

Стоит ли когда либо использовать #include <bits / stdc ++.h>?

я вот только не давно узнал про заголовочный файл #include <bits / stdc ++H> и зачал искать информацию по этой библиотеке

109
Как вывести двумерный массив корректно?

Как вывести двумерный массив корректно?

Пусть дано:Заполнить массив

122