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!"
