## Sorting Without Duplicates

### February 7, 2017

I think this is somebody’s homework problem:

Given an array of

nintegers, partition the array into sub-arrays, each in ascending order, and each without duplicates. For instance, given the array [2, 9, 1, 5, 1, 4, 9, 7, 2, 1, 4], the desired output is the array [1, 2, 4, 5, 7, 9, 1, 2, 4, 9, 1], where the intent is to have as many sub-arrays as the maximum frequency of any element, each sub-array as long as possible before starting the next sub-array of duplicates. If possible, perform the work in-place, in time either O(n) or O(nlogn).

Your task is to solve the sorting problem described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python. This solution is not in-place.

In Python. I believe it is O(n) (as Python counter dictionary takes n inserts) and the second for loop has exactly n elements.

@Rutger: You have to sort ctr in line 9, as the order is otherwise not defined. Try for example to multiply all entries of example with 101 and see what happens. (I get then [707, 404, 101, 505, 202, 909, 404, 101, 202, 909, 101])

A sort (could be in-place) followed by a reordering that is much like mergesort (but requires not only ordered input but a disjoint split, because I was not able to deal with ties correctly when combining the parts). It might be O(n log n), even in the worst case, and it might not be impossible to do in-place or with less space than here. The combination step attempts to pick a large element whenever possible; it seemed to work for many examples after I disallowed ties. This also is in Python.

I don’t think an O(n) solution is possible. If it was, you could use it to construct an O(n) sort of any array without ties, and apply it to arrays with ties by, for example, using the element’s original index to break them.

Anyway, because of the way its “transpose” function behaves, the Haskell solution is almost embarrassing: we can sort the array, group the elements, use transpose to turn it into a list of the correct subarrays, and concatenate the whole thing together:

Inspired by@Kevin another Python solution.

Here’s a Haskell version in the REPL. It’s not in-place.

[…] the comments to the previous exercise, reader Kevin gave a beautiful solution in Haskell; it sorts the input items, groups them into […]

Uses ‘key’ function of the built in ‘list.sort()’ method to sort the list into the desired order, in-place.

The trick or insight is to generate a key for each item in the list that reflects the number of times that item has been seen as well as the item itself. For example, in the test sequence below the three 1’s would get keys: (0,1), (1,1), (2,1).

The dd is a ‘defaultdict’ that holds an ‘itertools.count()’ counter for each unique value in the list. The key function takes a list item and returns a tuple (next value of the counter associated with that item, item).

Complexity is O(n log n). (The key function is called once for each element in the list, O(n). Sorting is O(n log n)).