Перегородка Ломуто, стабильная или нет?

Question

Я пытался искать в Интернете и в своей книге алгоритмов, если конкретное решение Lomuto раздела QSort * стабильно или нет (я знаю, что версия Хоара нестабильна), но яне нашел точного ответа.
Итак, я попытался привести те же примеры, и они кажутся стабильными.Но я не демонстрировал это.Не могли бы вы помочь мне?Если это не стабильно, не могли бы вы найти пример ввода?

Answer 1

Я собираюсь интерпретировать «Быструю сортировку с разделом Ломуто» как ссылку на алгоритм из здесь (слайды 21–22) .

Этот алгоритм нестабилен в массиве [ a , b , c ] где c <<em> a = b .

---

Я нашел этот контрпример, реализовав алгоритм Quicksort в Python, чтобы (подобно встроенной сортировке Python) он выполнял функцию key.Предоставляя соответствующую ключевую функцию, я могу заставить сортировку думать, что некоторые элементы идентичны, но я все еще могу различать их.Тогда это просто вопрос перестановок и определения нестабильности.Приведенный ниже код, конечно, не исчерпывает возможные тесты (можно попробовать более двух идентичных элементов или несколько наборов идентичных элементов), но в данном случае это было достаточно хорошо.