Раздел Hoare: эта реализация более/менее эффективна, чем стандартный алгоритм разбиения?

Question

В канонических реализациях алгоритма Hoare нам нужны начальные и конечные элементы массива в качестве аргументов, а algo поддерживает пару флагов для начала и конца многораздельного массива. Вот некоторые стандартные impls я нашел: QuickSort and Hoare Partition Hoare Partition Correctness in java

Теперь, я сделал следующее, и протестировали его с несколькими случайными массивами. Я не совсем уверен, что я сделал что-то не так - есть ли какие-то недостатки в этой реализации? Это как бы интуитивно чувствует себя очень похоже на вышеприведенные реализации, за исключением того факта, что он принимает меньше аргументов. Имеет ли она лучшую/худшую производительность (даже незначительно) по сравнению со стандартной реализацией? (Несмотря на то, да, оба из них O (п))

(MATLAB)

function partition(m_input) 
pivot = m_input(1); 
size = length(m_input); 
flag = 1; 
k = 1; 
    while(k<=size) 
     if(m_input(k)>pivot) 
      swap(m_input(size), m_input(k)) 
      size = size-1; 
     else 
      swap(m_input(k), m_input(flag)) 
      flag =k; 
      k=k+1; 
     end 
    end 
end 

Edit: вход изменен m_input.

Answer 1

Я всегда предпочитаю стандартную реализацию Хоара. Если вы посмотрите на это, это не очень интуитивно, но оно имеет видимое преимущество: меньшее количество свопов. Хотя ваша реализация эффективно всегда выполняет N сравнений и N свопов, реализация Hoare выполняет только N сравнений, но она не меняет местами, если она не нужна.

Разница значительна в некоторых сценариях. Сначала в случае, когда вы используете среду, где свопы или назначение переменных/объектов являются дорогостоящей операцией. Например, если вы используете C/C++ с массивами объектов. Другими типичными примерами, где реализация раздела Хора лучше, если многие элементы в вашем массиве имеют одинаковое значение или когда массив почти отсортирован и ему нужно просто поменять несколько элементов. В этом случае версия Хоара практически не свопит, в то время как вам еще нужно поменять N элементов, которые принимают инструкции назначения N * 3.