algorithm - Can an array be grouped more efficiently than sorted? -
while working on example code algorithm question, came across situation sorting input array, though needed have identical elements grouped together, not in particular order, e.g.:
{1,2,4,1,4,3,2} → {1,1,2,2,4,4,3} or {1,1,2,2,3,4,4} or {3,1,1,2,2,4,4} or ...
which made me wonder: is possible group identical elements in array more efficiently sorting array?
on 1 hand, fact elements don't need moved particular location means more freedom find order requires fewer swaps. on other hand, keeping track of every element in group located, , optimal final location is, may need more calculations sorting array.
a logical candidate type of counting sort, if array length and/or value range impractically large?
for sake of argument, let's array large (e.g. million elements), contains 32-bit integers, , number of identical elements per value 1 million.
update: languages support dictionaries, salvador dali's answer way go. i'd still interested in hearing old-fashioned compare-and-swap methods, or methods use less space, if there any.
yes, need create dictionary , count how many elements of each time have. after iterate on keys in dictionary , output key same number of time value of key.
quick python implementation:
from collections import counter arr = [1,2,4,1,4,3,2] cnt, grouped = counter(arr), [] # counter create dictionary counts number of each element k, v in cnt.iteritems(): grouped += [k] * v # [k] * v create array of length v, has elements equal k print grouped this group elements in o(n) time using potentially o(n) additional space. more efficiently (in terms of time complexity) sorting achieve in o(n logn) time , can done inplace.
