3
$\begingroup$

I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. Specifically, there is one pair of items for which the comparator function consistently gives the wrong result.

What is a efficient n*log(n) sorting algorithm that will be robust to this faulty comparison? By robust, I mean that every item is off by at most k spots from its true position, for some reasonably small k.

If possible, I'd like it to be robust in the worst case (faulty comparison chosen adversarially), but I'll settle for robust in the average case.

An example robust algorithm (that's not efficient), would be to make all n*(n-1)/2 pairwise comparisons, and place each item by how many of the comparisons they won. Then, no matter what comparison the adversary makes, each items index will be off by no more than k=1.

An example of a NON-robust algorithm is quicksort, because the adversary could just choose the largest item to be on the wrong side of the first pivot, making it on average n/2 spots off from its correct index.

$\endgroup$

3 Answers 3

1
$\begingroup$

I think I've thought up a solution.

First, do a first pass with any decent sorting algorithm you want (like quicksort), which should, at worst, result in only one item that's significantly far from where it should be.

Then, choose a width h that's at least 5.

for i from 0 to n-h, we look at the group of h items at i, i+1, ..., i+h-1. We make all h*(h-1)/2 pairwise comparisons in that group, and rearrange them by who won the most comparisons. We then increment i and move onto the next group.

Afterwards, we do the same thing, but going backwards from i=n-h to i=0.

These two extra passes will bubble up/bubble down the displaced item to be in the correct area, and uses the extra comparisons in a group of h to override the faulty single comparison.

The final number of comparisons will be O(n*log(n)) + n*h*(h-1)/2. Not sure how much better you can do.

This method also works (I think) for more than one faulty comparison. All you need to do is make sure that h is large enough to override those faulty comparisons.

$\endgroup$
1
$\begingroup$

It seems that this tends to be referred to as "noisy" comparison / information rather than faulty.

This paper specifically analyzes various sorting algorithms "robustness" in the context of faulty comparisons and shows both how it affects time/comparisons and the accuracy of the final result. According to their results, merge and quick sorts are the best traditional sorting algorithms. A swiss tournament gives better results, which makes sense since tournament systems are generally designed around the idea of imperfect comparisons. They get the best results from their own algorithm, which appears to be essentially tournament sort.

Sorting from Noisy Information may also be of interest.

$\endgroup$
0
$\begingroup$

If I give you an additional hint, that the two items that are consistently compared incorrectly are adjacent in the correctly sorted array, and I’ve sorted the array for you already so that only these two items are not correctly sorted, then there is no way for you to find out which pair is ordered incorrectly.

$\endgroup$
1
  • 4
    $\begingroup$ Yes, you are right. It means we can never get any algorithm for $k=0$. I think OP is settling for $k>0$ but some small constant. $\endgroup$ Jul 6, 2021 at 17:39

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.