2

A little rephrased, in the form of a game, real-life problem:

Suppose there is a set of elements {1, 2, ..., n}. Player A has chosen a single permutation of this set. Player B wants to find out the order of the elements by asking questions of form "Is X earlier in the permutation than Y?", where X and Y are elements of the set.

Assuming B wants to minimize the amount of questions, how many times would he have to ask, and what would be the algorithm?

  • This is essentially sorting the elements by their order in the permutation, so any comparison based sorting algorithm will do. I'm not sure whether there is a more efficient way. – user7043 Nov 2 '13 at 21:29
  • Seems insertion sort would be the best strategy for B. (Note: in this question, data movement is free. The only cost comes from pair comparison.) – rwong Nov 2 '13 at 22:35
5

This is exactly similar to a comparison based sorting problem. That is, we have all the elements in a scrambled order and wants to sort them using only comparisons (e.g. is X < Y)

As such, any comparison based sort algorithm will work. The performance of these varies, but we know for sure that we cannot get a running time below O(n*log(n)) for comparison based sorting. In many actual sorting scenarios, we can actually do better - but in this case we can only rely on comparisons, hence this is a hard limit on the running time.

Several algorithms exists for this problem:

                  Best case      Avg. case      Worst case     Worst case memory usage
Quicksort         O(n log(n))    O(n log(n))    O(n^2)         O(n)
Mergesort         O(n log(n))    O(n log(n))    O(n log(n))    O(n)
Heapsort          O(n log(n))    O(n log(n))    O(n log(n))    O(1)
Bubble Sort       O(n)           O(n^2)         O(n^2)         O(1)
Insertion Sort    O(n)           O(n^2)         O(n^2)         O(1)
Selection Sort    O(n^2)         O(n^2)         O(n^2)         O(1)

Apart from running time and memory usage, it should be mentioned that Insertion Sort is fastest for small arrays (optimized versions of mergesort might switch to Insertion Sort when arrays get small). Selection sort uses the smallest amount of actual swaps - which might be fast on systems where such swaps are expensive.

Some of the algorithms are unstable, meaning that equal elements are not guaranteed to come out in the order that we fetch them - however, this should not make any difference in this case, as there is no initial order in a set.

Finally, note that Quicksort has a worse worst case running time than Mergesort and Heapsort. However, for most inputs Quicksort often proves to be as fast or faster than these, due to the way you can actually implement the algorithm.

| improve this answer | |
  • 2
    The twist in this question is that data movements (swaps and copies) are free. The only cost (figure of merit) is the number of comparisons (number of questions asked). – rwong Nov 2 '13 at 22:37
  • Indeed. And I'm surprised at myself I didn't see this analogy :) By the way, do all those algorithms guarantee that we won't repeat the same comparison? – Maciej Stachowski Nov 2 '13 at 22:45
  • @rwong In practise, the cost of swaps might have some influence on the speed - the same goes for lots of other things, like CPU cache behavior and so on. However, the asymptotic running time is calculated from the number of comparisons in all case - hence, insertion sort will still only be good for small arrays. – nilu Nov 3 '13 at 8:32
  • @MaciejStachowski The number of comparisons and the asymptotic running time is essentially identical. If we compared every single element to each other, we would have O(n^2) comparisons - what is interesting to note, on the other hand, is that the best of these algorithms use less comparisons than this. Hence, we don't even need to compare each element. A more detailed analysis will further show that mergesort uses approximately 1/4 the number of comparisons of heapsort and avg. case quicksort - in practice the other algorithms are almost always just as fast or faster though. – nilu Nov 3 '13 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.