Re: puzzle

pete <pfiland@xxxxxxxxxxxxxx> writes:

> Richard Harter wrote:
> >
> > On Tue, 21 Jun 2005 13:23:53 GMT, pete <pfiland@xxxxxxxxxxxxxx> wrote:
> >
> > >An simple O(n*log(n)) solution for floating types
> > >would be to heapsort the array
> > >and do a sequential check for equality.
> >
> > And, of course, one can do it in O(n) time and O(1) space without the
> > xor trick. To quote someone (me):
> >
> > "If the array may be rearranged then we can again find the singleton
> > with O(1) space and O(n) time. The general idea is to select a pivot
> > value and then partition the array into elements smaller than the
> > pivot, equal to the pivot, and larger than the pivot. If the pivot is
> > the singleton we are done; otherwise repeat on the partition having an
> > odd number of elements."
>
> I think that algorithm suffers from the same O(n * n)
> worst case as simple quick sort.

Richard's algorithm is making use of finding the median
value of the array, which can be done in O(n) time. If you
can guarantee that the array is split nearly in half each
time, then it's possible to subdivide and zero in on the
unique element in O(n) time; using the median as the pivot
value provides that guarantee.


> It's possible that in a worst case,
> that all of your even sized partitions
> might be two elements in size.
> In that case, the partioning will be O(n),
> and the iterations will be O(n).

At each step there are only two partions - the values larger
than the pivot, and the values smaller than the pivot. We
take care to exclude the pivot pair from the partitions, or
if there is no pair value for the pivot then that's the
unique element. With an odd number of elements to start
with and an even number of elements removed, the two
partitions must have an odd number of elements in one case
and an even number in the other case.

The partition with the odd number of elements has the unique
element value, and can't have more than (K+1)/2 elements if
the array being divided had K elements. (In fact, it can't
have even as many as (K+1)/2 elements, but it certainly
can't have *more* than (K+1)/2 elements.)

So the algorithm really does have a worst case performance
that is

O( n + n/2 + n/4 + ... ) = O( n ).

[And, may I add to Richard: clever algorithm!]
.

Relevant Pages

  • Re: Fastest way to sort
    ... If we assume there is no duplicated values, and if we assume we are at the stage of the algorithm where the partitions are made, consider those partitions: A and C such that element a is in A are such that ab (b = the pivot). ... No element a in A would further interact with any element c in C, and vice-versa, by virtue of what a partition is. ... So, since the "recursive sorts" stage does not involve the actual pivot, a, and since the "2-way partition" stage seems to involve at most one comparison between the pivot and any other element a, I don't see why the 'basic' quick sort algorithm could involve two given elements compared together more than once, ever. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: puzzle
    ... >> "If the array may be rearranged then we can again find the singleton ... >> value and then partition the array into elements smaller than the ... >> pivot, equal to the pivot, and larger than the pivot. ... median that are strictly Oin some circles) so we can ...
    (comp.programming)
  • Re: puzzle
    ... "If the array may be rearranged then we can again find the singleton ... value and then partition the array into elements smaller than the ... pivot, equal to the pivot, and larger than the pivot. ...
    (comp.programming)
  • Re: puzzle
    ... > "If the array may be rearranged then we can again find the singleton ... > value and then partition the array into elements smaller than the ... > pivot, equal to the pivot, and larger than the pivot. ...
    (comp.programming)
  • Re: Partitioning an array .
    ... an algorithm to partition an array of integers into 2 sub-arrays,such ... You all think I'm paranoid, ...
    (comp.programming)