Быстрая сортировка для сортировки массива объектов по определенному члену C ++

Question

class Foo
{
    public:
        int num;
        int other;
};

int main()
{
    Foo bar[10].num = {1, 9, 3, 5, 1, 6, 10, 0, 6, 3};

    //quicksort(bar)

    return 0;
}

Я хочу написать функцию быстрой сортировки, которая упорядочивает массив 'bar' по возрастанию 'num'.Не совсем уверен, каков наилучший подход, поскольку я никогда не писал быстрой сортировки.Я посмотрел некоторые примеры кодов, но я не вижу, как изменить их для этого случая.Сортировка по месту, выполняемая путем передачи указателей на первый и последний элементы массива, не работает, так как сортируется только элемент 'num', а не весь объект.Разделение массива объектов на нижний массив, сводный и верхний массивы и рекурсивная сортировка каждого выглядит многообещающе, но я не уверен, как будет работать передача значений ...

Любая помощь очень ценится.Извините, если об этом уже спрашивали.

Answer 1

Сначала вы пишете функцию (или функтор) для сравнения ваших объектов по любому значению, которое вы хотите.Нужно взять два объекта и вернуть бул.Он должен возвращать true, если первое должно предшествовать второму, иначе false.Затем передайте это в std :: sort.

struct compare_Foo_by_num
{
    bool operator() (const Foo & lhs, const Foo & rhs) { return lhs.num < rhs.num; }
};

int main()
{
    Foo bar[10];

    std::sort(bar, bar+10, compare_Foo_by_num());
}

Answer 2

Вы можете перегрузить operator<, чтобы сравнить нужный элемент, а затем использовать std::sort.

#include <algorithm>

class Foo
{
public:
    int num;
    int other;
};

bool operator<(const Foo& x, const Foo& y)
{
    return x.num < y.num;
}

int main()
{
    Foo bar[10] = {{1, 5}, {9, 2}, {3, 0}, {5, 7}, {1, 3}, {6, 4}, {10, 8}, {0, 9}, {6, 2}, {3, 5}};
    std::sort(bar + 0, bar + 10);
}

Обратите внимание, что для инициализации Foo нужны два числа, а не только то, которое вас интересует при сортировке.

Если вы не можете или не хотите перегружать operator< для Foo, другие опции включают передачу старого доброго указателя функции стиля C или объекта функции стиля C ++ в качестве третьего параметра std::sort.

Answer 3

Другой альтернативой является использование std :: sort с лямбда-выражением:

int main()
{
    Foo bar[10] = {{1,5},{9,2},{3,0},{5,7},{1,3},{6,4},{10,8},{0,9},{6,2},{3,5}};

    std::sort(bar, bar + 10, [](const Foo &x, const Foo &y) {
        return x.num < y.num;
    });
}

Answer 4

Если вы непреклонны в реализации собственной быстрой сортировки, я советую посмотреть это видео, чтобы лучше визуализировать алгоритм. Хотя вы никогда не писали быструю сортировку, вам, возможно, будет легче реализовать ее после просмотра. http://www.youtube.com/watch?v=vxENKlcs2Tw