CODEWITHSUNDEEP
c++algorithmsorting
worstcoder
worstcoder

Reputation: 61

Sorting using a three number comparator

I have an array of size n waiting to be sorted. But different from ordinary sorting problem, I'm constrained to use a specific comparator, which receives three numbers and tells the maximum and minimum of the three. My goal is to use the comparator as few times as possible before completely sorting the array. What strategy can I use?

Thanks for any help!

Upvotes: 2

Views: 662

Answers (3)

worstcoder
worstcoder

Reputation: 61

Well, I get an brilliant idea. Using 4-way mergesort and loser tree to optimize, the times of using the comparator can be reduced to less than 0.5nlog₂n, by my rough estimate.

Upvotes: 0

kaya3
kaya3

Reputation: 51063

Since your three-way comparator can be implemented by three calls to a normal comparator, that means we can't improve on any normal sorting algorithm by a factor of more than 3. A more careful argument shows that, because each three-way comparison gives us log₂ 6 ≈ 2.585 bits of information, we can't improve by a factor of more than that. Intuitively, when sorting with a normal comparator you might compare a <= b and b <= c, and therefore not need to compare a and c anyway; so the possible speedup factor could be as small as 2.

So asymptotically, we're still looking for an O(n log n) algorithm, and the question is how to exploit the comparator to do fewer comparisons by at least a factor 2. The "obvious" thing to try first is modifying an existing comparison-based sorting algorithm; a good candidate is bottom-up heapsort, which does about n log₂ n comparisons in the average case, and 1.5 n log₂ n in the worst case (Wikipedia). This beats the standard quicksort algorithm, which does about 1.39 n log₂ n comparisons in the average case (Wikipedia).

The algorithm works using two basic operations on a heap, "sift down" and "sift up".

  • The "sift down" operation requires comparing a parent element with its two children, to see if the parent element is greater than or equal to both its children, or if not, which child the parent should be swapped with. We can use the three-way comparator to compare the parent with both children at once.
  • The "sift up" operation compares a child with its parent, and swaps them if they are out of order; this is then repeated all the way up to the root node. We can use the three-way comparator to compare the child node with its parent and its grandparent at once.

The heapsort algorithm only calls the comparator within those two operations, and for both operations the three-way comparator can be called fewer times by a factor of 2. This isn't necessarily the best you can do, but it starts from a very efficient algorithm, and matches the worst-case speedup factor given by intuition.

Upvotes: 2

Leontyev Georgiy
Leontyev Georgiy

Reputation: 1315

Well, I came up with an idea.

Let's remember how quicksort works:

  • First, we locate a sort of a median value (pick up (a[0] + a[N-1])/2 if you're too lazy =3).
  • Then, we divide an array by two on the condition of being less or greater than median.
  • At last, we run the algorithm recursively on each of two subarrays

Using your comparator, you can speed up your second phase twice by processing two values at once:

  • compare(median, a[2 * i], a[2 * i + 1])
  • if min is median, both are greater and go to the right subarray
  • if max is median, both are less and go to the left subarray
  • if neither is median, min goes left, and max goes right

After that, run recursive part of the algorithm as usual.

Upvotes: 1

Related Questions