Поменять условие в процедуре быстрой сортировки (Lomuto)?

Question

Я реализовал быструю сортировку из книги Введение в алгоритмы.книга определяет процедуру следующим образом

Однако Я не вижу требования сравнения менее равного в строке 4, не долженДостаточно только сравнения меньше .

Для проверки я написал следующую программу, и она корректно работала на тестируемом наборе данных.

private fun partition(start: Int, end: Int, arr: Array<Int>) : Int{
        var pivotIndex = end
        var maximumElementIndex = start
        for(index in start until end){
            if(arr[index]<arr[pivotIndex]){
                val temp = arr[index]
                arr[index] = arr[maximumElementIndex]
                arr[maximumElementIndex] = temp
                maximumElementIndex++
            }
        }

        val temp = arr[maximumElementIndex]
        arr[maximumElementIndex] = arr[pivotIndex]
        arr[pivotIndex] = temp
        return maximumElementIndex
    }

Я проверил ее на следующихвходные данные

• массив со всеми равными элементами
• отсортированный массив
• отсортированный в обратном порядке
• множественный набор случайных данных

так чего мне здесь не хватает?

Answer 1

Существует больше различий, чем использование <=.Он также инициализирует i = p-1;, а последний своп swap(A[i+1], A[r]);.Это просто вариант схемы разделов Lomuto.Ваш пример кода соответствует этому в статье Wiki:

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

Обратите внимание, что обе схемы являются наихудшим случаем с уже отсортированными данными, обратно отсортированными данными и всеми равными элементами, как только разделуменьшает размер раздела на 1 с каждым уровнем рекурсии.Использование среднего значения в качестве сводного и его свопирование до конца решает проблему с отсортированными или обратно отсортированными данными, но Lomuto обычно ухудшается с увеличением числа равных элементов.

Схема Хоара, использующая средний элемент, обычно улучшается с увеличением количества дубликатов.Нет необходимости менять местами элементы, равные значению сводных данных, но разделение приближается к идеальному случаю разбиения равномерного размера по мере увеличения числа дубликатов, а кэш помогает с ненужным обменом.

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme