Hoare partition : is this implementation more/less efficient than the standard partition algorithm?

Question

In the canonical implementations of the Hoare algorithm, we need the starting and ending elements of the array as arguments, and the algo maintains a couple of flags for the start and end of the partitioned array. Here are some standard impls I found: QuickSort and Hoare Partition Hoare Partition Correctness in java

Now, I did the following, and tested it out with a few random arrays. I'm not quite sure if I've done anything wrong - are there any holes in this implementation? It sort of intuitively feels very similar to the implementations above, except for the fact that it takes less arguments. Does it have a better/worse performance (even marginally so)compared to the standard implementation? (even though, yes, both of these are O(n))

(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 : input changed to m_input .

Suggestion. It's not likely to hurt anything, but you still might not want to have a variable called `input`, which is also the name of [a common function used to obtain user input](http://www.mathworks.com/help/matlab/ref/input.html). — horchler, Jul 16 '13 at 14:30

score 0 · Answer 1 · answered Apr 12 '14 at 00:06

I always prefer the standard Hoare's implementation. If you look at it, it is not very intuitive, but it has a visible advantage: Less number of swaps. While your implementation effectively always does exactly N comparisons and N swaps, the Hoare's implementation does only N comparisons, but it does not swap anything if it is not needed.

The difference is significant in some scenarios. At first in a case you use environment where swaps or assignment of variables/objects is a costy operation. For example if you use C/C++ with arrays of objects. Another typical examples where Hoare's partition implementation performs better if when many of the items in your array are of the same value or when the array is almost sorted and needs just to swap a few items. In that cases Hoare's version performs almost no swaps, while your one still needs to swap N items, which takes N*3 assignment instructions.

Hoare partition : is this implementation more/less efficient than the standard partition algorithm?

1 Answers1