O(nloglog n) sorting

[orbita]

Hi, can anyone help me with this question:
Given an array of n integers with many duplications. The number of distinct integers in the array is at most log n.

a) Give an O(nlog n) algorithm that outputs the distinct integers in the array. The output is store in an array B. Size of be is at most log n.

b)Give an O(nloglog n) algorithm that sort the array. (hints: modify (a) so that binary search can be applied. Take special care on insertion.)


This is one of my assignment questions. I think I have solved question a) but I'm stuck with (b) for almost 2 days.
Please help me solve it. Thank you so much.

[Hnefi]

Tricky.

Since a general sorting algorithm in O(nlog(log(n))) time is impossible, you must use the structure of the problem to create some shortcuts.

One way to solve the problem, assuming that the elements in the array are discrete, is to do a bucketsort or radix sort. This is obviously not what was intended by your teachers, but it will sort the array in O(n+m) time (m being the difference between the largest and smallest element), which is generally better than O(nlog(log(n))).

But your teacher had something else in mind, and it's usually better to humor the teacher than trying to find a "unique" solution. Perhaps something like this:

Do a quicksort on array A and save the results in another array (a list would be simpler to implement, but an array is possible as well). However, if there already is another element in Array B which is equal to the one you are currently sorting, don't insert the new element. Since quicksort finds the elements closest to the one you are trying to insert into a sorted list/array, determining whether an equal element already exists is O(1) and adds no complexity.

Normally, a quicksort runs in expected time O(nlog(n)), which isn't good enough. But the log(n) part is, if I recall correctly, determined by how many elements have already been sorted into array/list B. Since that amount is reduced from n to log(n) by the added operation mentioned above, this solutions should run in expected O(nlog(log(n))) time - worst case is much worse, but I don't think it's possible to create a solution with worst case time O(nlog(log(n))).

The actual code you'll have to write yourself, of course. It IS an assignment, after all ;)

[Hnefi]

Now that I look at it, I realize the above solution isn't complete since quicksort doesn't bother with finding elements that are close to the one you are sorting at the moment, and doesn't sort its sublists. Sorry about that.

The only solution I can think of is to simply use a heapsort instead. When constructing the heap, you will do size comparisons with other elements. Since the comparison is already made, you can deal with the case of two elements being equal without adding to complexity. Very straightforward if you know how to build a heap.

Building a heap normally takes O(log(n)) and doing a heapsort takes O(nlog(n)), but since the maximum height of the heap is reduced from log(n) to log(log(n)) with this method, the algorithm should run in O(nlog(log(n))).

Someone please correct me if I'm wrong again.:blush:

[Hnefi]

I believe you're wrong about heapsort. To begin with, constructing the heap in a normal heapsort takes O(nlog(n)), not O(n).

If we assume the duplicate numbers are roughly evenly distributed (calculations are expected time, right?), the size of the heap will, at any one point in time, be only of depth log(log(n)) instead of the normal case log(n). This should mean that the heap will take O(log(log(n))) time to construct in this case. Extracting the numbers and placing them into the sorted array takes O(log(n)). If I'm not doing something terribly wrong here, this version of heapsort should therefore run in O(log(n)log(log(n))) expected time, which qualifies as O(nlog(log(n))) since log(n)log(log(n)) < nlog(log(n)).

[RoboTact]

Hi, can anyone help me with this question:
Given an array of n integers with many duplications. The number of distinct integers in the array is at most log n.

a) Give an O(nlog n) algorithm that outputs the distinct integers in the array. The output is store in an array B. Size of be is at most log n.

b)Give an O(nloglog n) algorithm that sort the array. (hints: modify (a) so that binary search can be applied. Take special care on insertion.)


This is one of my assignment questions. I think I have solved question a) but I'm stuck with (b) for almost 2 days.
Please help me solve it. Thank you so much.Like in a), look through original array. Support an array of already found different values, in sorted order. Picking each new item from original array, search it in second array using binary search, O(log(log(n))). If it's there, go on. If it's not, insert it, which would take O(log(n)), at most log(n) times, so you have O(n*log(log(n))+log(n)*log(n))=O(n*log(log(n)))