TADM2E 4.23

From Algorithm Wiki
Revision as of 18:13, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Problem

4-23. We seek to sort a sequence S of n integers with many duplications, such that the number of distinct integers in S is O(log n). Give an O(n log log n) worst-case time algorithm to sort such sequences.

Solution

With a self-balancing binary search tree, we can achieve O(log k) search and insertion (where k is the number of elements in the tree).


1. For each element in the sequence S, try and insert it into the tree.

- If the element is present, we increment a count variable stored at a node.

- If the element is not present, we insert the node and set the count = 1.


2. Traverse the tree in order and add elements according to the count.


Since the tree is guaranteed not to exceed log n elements, search and insertion take O(log log n).

Thus, this entire algorithm takes O(n * log log n + log n) = O(n * log log n) as required.