Re-ordering an array so it is grouped by identical elements

Question

I'm looking at a problem with processing an array, which can be easily solved with sorting. However, my requirement is actually more relaxed than a full sort: I only need the guarantee that, if there are any identical elements in the array, they will be found adjacent to each other in the array.

Is there an algorithm for re-ordering an array such that it meets the above criteria, which would be more efficient that simply doing a full sort?

Answer 1

If the order is not a problem you can try any of the hashing techniques. All hashing techniques generally lead to grouping of similar items. For each item in the array just use a hash function and all the elements are grouped according to the function that you define.