sortUniq

[H. S. Teoh via Digitalmars-d]

On Thu, Jan 22, 2015 at 11:52:18PM +0000, Vladimir Panteleev via Digitalmars-d wrote:
> On Thursday, 22 January 2015 at 23:35:32 UTC, H. S. Teoh via Digitalmars-d
> wrote:
> >On Thu, Jan 22, 2015 at 02:51:38PM -0800, H. S. Teoh via Digitalmars-d
> >wrote:
> >>Wait, if R1 and R3, after the recursion, are sorted and contain only
> >>unique elements, doesn't that mean that we can just collapse R2 into
> >>a single element along with the endpoints of R1 and R3? So if
> >>R1[$-1] < pivot, then we're done, otherwise coalesce it with the
> >>pivot, and likewise with R3[0].
> 
> I'm pretty sure that when Andrei said:
> 
> >>> C. Sort-move-unique R2 into the portion after R11, obtaining > the
> >>> result.
> 
> He meant R3, not R2. R2 is obviously collapsed to one element (the
> pivot).

Ah, that's why I misunderstood him.


> >Working proof of concept:
> 
> I think this will actually have worse performance than sort+uniq,
> since you're now shuffling half of the elements at each recursion
> depth - an additional O(n log n).

That's what I thought. At each step, you have to coalesce the elements
by copying `right` over. So that adds up to quite a cost.

Actually, I just realized that the code has an unnecessary check for
left[$-1] being equal to pivot: this is actually impossible, since
partition() makes sure that the left half of the range is strictly less
than the pivot, so it cannot possibly contain the pivot. So we can
eliminate that check. But it doesn't solve the problem of excessive
copying.

Hmm... actually, I think it might be possible to modify partition so
that it eliminates duplicated pivots for you. However, this still
doesn't solve the recursive case where `left` might have shrunk, thus
necessitating `right` be shifted over afterwards.

A modified heapsort might be a better candidate for uniqueSort() than
quicksort, it looks like.


T

-- 
Music critic: "That's an imitation fugue!"