I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted.

E.g. if input is

array = ["a", "a", "c", "b", "c"]

then output

groupby(array) = ["a", "a", "c", "c", "b"]


groupby(array) = ["c", "c", "a", "a", "b"]

etc. The point being the final order of the array isn't important; the only requirement is that identical elements have to be placed contiguously.

One algorithm that is inspired by quicksort is to pick an element, called it pivot, and divided the array into 3 segments with the first segment being all elements that equal pivot; and the other two begin those are "less than" and "greater than" pivot. Elements within each segment have to be placed contiguously.

The segmentation can be achieved in n time using a simple adaption of the pivoting in quicksort and then apply the algorithm recursively on the "less than" and "greater than" segment.

Is this algorithm well known and has a name? Or is it a novel algorithm?

  • $\begingroup$ Isn't that just an ordinary quicksort with a "fat partition"? $\endgroup$ – Ilmari Karonen Oct 31 '17 at 0:49
  • $\begingroup$ The algorithm doesn't need to sort. You don't have to use less than or greater than, actually any method that can break them into two groups is fine $\endgroup$ – xiaodai Oct 31 '17 at 2:54
  • $\begingroup$ OK, but you still need to ensure that the elements with a given value always end up on the same side of the pivot, not split between the two sides, right? Still sounds (effectively) like sorting to me, but maybe I'm just missing something. Perhaps it would be clearer if you could provide a (pseudo)code version of your algorithm. $\endgroup$ – Ilmari Karonen Oct 31 '17 at 9:45
  • $\begingroup$ @IlmariKaronen yes the method have to be determinstic $\endgroup$ – xiaodai Oct 31 '17 at 9:48

Asymptotically and under usual assumptions, the problem you state is as hard as sorting, by reduction from duplication.

If you had a $o(n \log n)$ algorithm to solve your problem, you could combine it with a constant number of array scans to produce a $o(n \log n)$ time procedure to test whether the array contains a pair of identical elements, in contradiction with the well-known $\Omega(n \log n)$ lower bound on that problem.

I don't think there's much to be gained with custom-tailored algorithms in practice, either: a well-optimized implementation of a generic sorting algorithm should be -- without further assumptions -- as efficient as you can get.

  • $\begingroup$ "Asymptotically and under usual assumptions, the problem you state is as hard as sorting, by reduction from duplication." No doubt it is true but is there a "mathematical" proof to show that this is true? $\endgroup$ – xiaodai Oct 31 '17 at 21:53
  • $\begingroup$ The one I outline is a proof. I only take for granted the bound for the duplicate problem, but that is a classical result, you can find a proof for example here: ac.els-cdn.com/0167642382900120/… (Misra, Jayadev, and David Gries. "Finding repeated elements." Science of computer programming 2.2 (1982): 143-152.) $\endgroup$ – quicksort Oct 31 '17 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.