Сравнение равных значений в быстрой сортировке

Question

Сравнение равных значений в быстрой сортировке

У меня есть объект, в котором есть три переменные: исходная вершина, конечная вершина и длина. У меня есть алгоритм быстрой сортировки, который сортирует объект по длине. Однако я хочу, чтобы, если я сравнил два объекта и их длины были равны, моя быстрая сортировка отсортировала объект с меньшей исходной вершиной перед объектом с большей исходной вершиной. Если они также равны, я хочу сравнить вершины назначения. Я хочу отсортировать большую целевую вершину перед ней с меньшей исходной вершиной. Все это будет сделано в массиве. Ниже моя реализация быстрой сортировки. Обратите внимание, что e [i] — мой объект, который содержит мои вершины и длину.

void quickSort(edge *e, int left, int right)
{
int i = left, j = right;
int temp, temp1, temp2;
while(i <= j)
{
while(e[i].getLength() < pivot)
i++;
while(e[j].getLength() > pivot)
j--;
if(i <= j)
{
temp = e[i].getLength();
temp1 = e[i].getEdgeSrc();
temp2 = e[i].getEdgeDes();
e[i].setLength(e[j].getLength());
e[i].setEdgeSrc(e[j].getEdgeSrc());
e[i].setEdgeDes(e[j].getEdgeDes());
e[j].setLength(temp);
e[j].setEdgeSrc(temp1);
e[j].setEdgeDes(temp2);
i++;
j--;
} //if statement
}///while loop
if(left < j)
quickSort(e, left, j);
if(i < right)
quickSort(e, i, right);

}

Может кто-нибудь знает, как / где выполнить сортировку вершин, если длины равны? Спасибо!

1

algorithm c++quicksort

Решение

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

Вам нужно создать функцию сравнения и вызывать ее, а не сравнивать длины. Вы не определяете pivot в любом месте вашего кода, но я предполагаю, что это тот же тип, который возвращается getLength(), Вам нужно будет изменить pivot так что это индекс. Затем вы пишете:

while (compareEdge(e[i], e[pivot]) < 0)
i++;
while (compareEdge(e[j], e[pivot]) > 0)
j--;

Ваш compareEdge Функция будет сравнивать длины. Если они равны, сравниваются вершины, как вы описали.

0

Источник

Accepted Answer

Лучше всего определить оператор сравнения для edge объекты, которые делают то, что вам нужно сделать:

class edge
{
/* ... */
public:

bool operator<(const edge &other) const
{
/* Length is first criterion: */
if (length < other.length)
return true;
/* Source vertex is second criterion: */
else if ((length == other.length) && (src < other.src))
return true;
return false;
}

/* ... */
};

И затем, внутри вашей быстрой реализации сортировки, вы используете этот оператор для сравнения edge объекты, а не доступ getLength() и т.д. напрямую:

while(e[i].getLength() < pivot)
i++;

становится

while(e[i] < pivot)
i++;

А также

while(e[j].getLength() > pivot)
j--;

становится

while(pivot < e[j])
j--;

Обратите внимание, что я только определил operator<не operator>Поэтому я предлагаю использовать только это. Кроме того, вы можете определить operator> также.

Обратите внимание, что выше я предполагаю, что pivot является ссылкой на текущий элемент поворота. Если это на самом деле целочисленный индекс для текущего стержня, вам нужно заменить его на e[pivot],

Отдельное примечание: вы можете использовать std::swap(e[i],e[j]); вместо длинной (и подверженной ошибкам) последовательности инструкций get- и set и временных переменных.

2