Подсчет Сортировка для набора

Question

Подсчет Сортировка для набора

Здравствуйте, я знаю, как работает сортировка couting, как ее реализовать, но можно ли реализовать ее в классе, который получил 3 атрибута и должен рассчитывать весь набор DisjointSet по определенному атрибуту.

Если так, допустим, у меня есть этот класс:

class myStructure {
public:
int m_id = -1;
myStructure* m_parent = NULL;
int m_sortie = -1;
int m_echeance = -1;

myStructure() {}

myStructure(int id, myStructure* parent, int sortie, int echeance)
: m_id(id), m_parent(parent), m_sortie(sortie), m_echeance(echeance)
{ }
};

Как я могу реализовать подсчет сортировки на m_echance.
Спасибо

0

c++counting counting-sort data-structures sorting

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Конечно, вы можете применить подсчет сортировки.
Это применимо к любому полю, которое может быть отображено целыми числами. В общем случае следует использовать сортировку подсчета, если диапазон значений (в вашем случае m_echeance) невелик.
Ниже приведен подход высокого уровня, чтобы сделать это

Допустим, ваши объекты хранятся в массиве A []

диапазон m_echeance равен [0, R-1]

Создайте массив count.
цикл по массиву A для подсчета частот объектов с различными значениями m_echeance.

что-то вроде count [A [i] -> m_echeance + 1] ++;

Получить кумулятивные частоты для массива count.
Копировать объекты во вспомогательный массив на основе совокупных частот.
Скопируйте обратно объекты из вспомогательного массива в исходный массив.

Надеюсь, поможет!

0