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