Как оставить заказ без изменений на равенство с использованием QSort

Question

Прямо из руководства QSort он говорит:

Если два члена сравниваются как равные, их порядок в отсортированном массиве не определен.

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

Я не уверен, как это сделать с помощью qsort. Я бы предпочел не использовать альтернативную библиотеку сортировки/перевернуть мою собственную.

Благодаря

-

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

Answer 1

qsort означает «Quick Sort», что является быстрым, но нестабильным алгоритмом сортировки. Предположим, что вы сортируете по возрастанию. В этом случае алгоритм сортировки называется стабильным, если он не будет заменять элементы, имеющие одинаковые ключи. Если он может менять элементы с одинаковыми клавишами, это нестабильно.

Существуют различные решения вашей проблемы; Я предложу двух из них здесь.

Решение 1

Вы можете найти в Википедии некоторые интересные идеи относительно stability of sorting algorithms, в том числе способ применения нестабильных алгоритмов, когда вы на самом деле нужно стабильное один: вы расширить сортировки ключевых: если вы например, сортировка с использованием целочисленного значения.

Предположим, что вы сортируете массив целых чисел. Вместо этого вы создаете структуру с двумя элементами: первая (KEY) является вашим целым числом.Второй (AUX_KEY) является уникальным номером. Перед сортировкой вы линейно устанавливаете AUX_KEY, чтобы отразить первоначальный заказ. При сортировке перейдите к qsort функции, которая будет сортироваться с использованием KEY, но вернется к использованию AUX_KEY, если два ключа равны.

Решение 2

Вместо использования Quicksort используйте устойчивый алгоритм, как merge sort, который вы, вероятно, имеете в среде программирования (например, вот FreeBSD manpage for mergesort, то же самое может быть доступна в других средах программирования под одно и то же имя - пожалуйста, проверьте), или, если вам не нужна слишком большая скорость, используйте insertion sort (который вы можете запрограммировать самостоятельно - это занимает несколько строк только в псевдокоде). Взятие сортировки вставки имеет квадратичную временную сложность (требуется время, пропорциональное n^2), тогда как mergesort и quicksort имеют временную сложность O (n log (n)).

Answer 2

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

Что вы можете сделать, это внедрение/с использованием другого алгоритма, или заставить их сортировать, как они были:

• Если сравнивать функция должна возвращать равенство, посмотрим, как они первоначально были отсортированы и сортировать их так же.

Answer 3

Вы по существу спрашиваете, как реализовать стабильную сортировку поверх нестабильной сортировки.

Существует мало что вы можете сделать: у вас есть только контроль над функцией сравнения, поэтому вам придется работать над этим.

Одной из возможностей является присоединение второго идентификатора ключа к каждому элементу массива, который соответствует исходному индексу этого элемента. Затем, если два элемента сравниваются равными, просто верните соответствующий порядок в соответствии с их исходными индексами.

Answer 4

Как GNU libc manual объясняет,

Единственный способ выполнить стабильный сорт с QSort должен сначала увеличить объекты с монотонным счетчиком некоторого вида.

Таким образом, если вы не можете изменить вашу функцию сравнения так, что объекты, которые в настоящее время считают «равными», может различаться, вы должны явно аннотировать объекты с индексами до сортировки и удаление индексов, когда вы закончите , Вы можете использовать что-то вроде

struct indexed { 
    void *obj; 
    int index; 
}