|
|
| Line 1: |
Line 1: |
| − | == Problem ==
| + | #REDIRECT [[UNTV]] |
| − | | |
| − | 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.
| |
