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"]
or
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?