sortUniq

[H. S. Teoh via Digitalmars-d]

On Thu, Jan 22, 2015 at 04:33:28PM -0800, Andrei Alexandrescu via Digitalmars-d wrote:
> On 1/22/15 4:26 PM, H. S. Teoh via Digitalmars-d wrote:
> >The question, though, is whether this hybrid recursion actually wins
> >us anything, since heapsort is known to be somewhat slower than
> >quicksort.  In the worst case, you choose a poor pivot and get*both*
> >the worst case of quicksort and the inferior performance of heapsort
> >compounded together.
> 
> The glass-half-full view of this is you combine the advantages of
> quicksort and heapsort :o).

Well, I've been in the field long enough to realize that putting things
together more often than not causes increase in complexity (usually
accompanied by poorer performance) rather than the other way round. It's
part of why algorithms research is so hard... but also so rewarding,
when you do hit upon a winning combination that actually reduces
complexity and/or improves performance.


> >Unless there's a way to modify heapsort to be more efficient as well?
> >
> >Actually, another idea occurred to me: suppose we modify partition()
> >instead, so that instead of partitioning in-place, it deposits
> >partitioned elements into a target (possibly overlapping) range. Then
> >we modify the right-recursion, so that its partitioning step actually
> >simultaneously moves the range over to the target area for us. Not
> >sure if this will eliminate the copying cost, but it might, since
> >partition has to traverse the entire subrange anyway.
> 
> That's interesting!
[...]

Here's a crude first-impressions sketch of how this modified partition
might work:

- As we move up the range, if the current element is less than the
  pivot, we deposit it into the growing left partition which is in the
  target location rather than the original location.

- If the current element is equal to the pivot, we ignore it (this
  eliminates the pivot and its duplicates altogether from the left/right
  partitions).

- The tricky case is if it's greater than the pivot. In the normal
  quicksort partition, we do nothing -- it will get moved later if it's
  occupying the space that belongs to the left partition. However, in
  our case, we need to move it *somewhere*, otherwise it will get lost
  if it doesn't lie in the overlapping area of the target range and the
  range being partitioned.

  One idea is to move it to the end of the target range, so that the
  two partitions grow from opposite ends of the target range, and they
  should meet in the middle (otherwise the target range is of the wrong
  size). However, the details of how this can be done is still murky.
  I'll have to think more about this.


T

-- 
Talk is cheap. Whining is actually free. -- Lars Wirzenius