I am working on a question from The Algorithm Design Manual and need some help.

Question

I am working on a question from The Algorithm Design Manual and need some help.

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(logn). Give an O(nloglogn) worst-case time algorithm to sort such sequences.

You can view the question here:
http://www2.algorithm.cs.sunysb.edu:8080/mediawiki/index.php/Sorting-searching-TADM2E

Explanation / Answer

I will use a modified version of quick sort. The idea is that, when you choose a pivot, for elements greater or less than pivot, partition as you do in a normal quick sort, however if you find elements equal to pivot, just maintain a count of such elements and dont add them to any partition. Finally, when partition is complete, place the pivot in correct position and place that many duplicates next to it as you counted earlier. For the next recursive calls, call the quick sort for the elements left to, and then for the elements right to the whole group of pivot duplicates. In such a way the recursive calls go only as deep as O(log k) (where k is the number of distinct elements) which is equivalent to log log n as k = log n in you case. And in each recursive step, you do O(n) operation hence the complexity comes to be O(n log log n). Here is the pseudo code: function quicksort('array') if length('array') = 1 return 'array' // an array of zero or one elements is already sorted select and remove a pivot value 'pivot' from 'array' create empty lists 'less' and 'greater' 'duplicates' = 0 for each 'x' in 'array' if 'x' = 'pivot' then append 'x' to 'less' else if 'x'>= 'pivot' append 'x' to 'greater' else 'duplicates' = 'duplicates' + 1 'pivot_list' containing 'pivot', 'duplicates' number of time return concatenate(quicksort('less'), 'pivot_list', quicksort('greater')) // two recursive calls

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.