random — (C ++) Добавить случайность к быстрой сортировке на равных элементах

Question

random — (C ++) Добавить случайность к быстрой сортировке на равных элементах

Я использую следующий код для сортировки элементов в std.vector

struct element {
int order;
int someValue;
};

int comp( element a, element b ) {
if (a.order < b.order)
return true;
return (rand() % 2) == 0;
}

vector.quickSort(comp);

этот код правильный, если я пытаюсь добавить случайность на элементы, которые имеют одинаковые порядок значение

2

c++quicksort random

Решение

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

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

Источник

Accepted Answer

Этот код правильный.

Вы должны действительно написать тест с некоторыми данными, чтобы проверить это.

Если бы вы написали тест, вы бы увидели что-то не так и узнали бы почему, если мы посмотрим на

if (a.order < b.order)
return true;
return (rand() % 2) == 0;

Вы можете видеть, что a.order > b.order case отсутствует, поэтому он будет некорректно работать в этом случае, мы можем исправить это, выполнив это вместо этого, вместо этого сосредоточив внимание на исключительном случае и оставив два других случая их поведению по умолчанию (проверка порядка):

if (a.order == b.order)
return (rand() % 2) == 0;
else
return a.order < b.order;

3