3

Does a comparison sort have to compare the A[i] largest and A[i+1] largest values? I think any comparison sort must, but I'm not sure. I've checked out mergesort, insertion sort, and quicksort and in each of them the A[i] largest and A[i+1] largest values have to be compared.

2
  • Looking at various algorithms may give you clues about how to prove the general rule, but, "all algorithms are such," does not follow from, "some algorithms are such." This is a fallacy called "affirming the consequent." You have to reason it through.
    – erickson
    Oct 30, 2008 at 17:48
  • You mean ith and (i+1)th largest values Oct 30, 2008 at 17:51

8 Answers 8

2

Every correct algorithm has to compare adjacent cells, unless they are equal. Proof: Assume otherwise. A[i] and A[i+1] in the final array have not been compared (A[i] < A[i+1). What happens if their positions are swapped in the original array? All the comparisons made by the algorithm give the same results as in the original run(*), therefore it executes the same permutation, therefore their final positions are swapped, so it makes the algorithm incorrect.

(*) This follows from the fact that A[i] and A[j] are adjacent.

1

Yes, in any comparison sort, adjacent cells will always be compared to each other. See this page for more precise definitions of the lower bounds of comparison sort.

1

Yes they do, unless there are at least 3 identical elements. Without doing that, there's no way to guarantee you have a sorted properly. The only way you avoid comparing all pairs is by the transitive principle.

A[i] > A[j] and A[j] > A[k] implies A[i] > A[k].

With distinct consecutive values, there's no intermediate values to help you avoid the comparison.

1

Shell sorts don't compare adjacent cells. This is how they gain some efficiency versus the slow sorts (bubble, insertion, selection).

0

Quicksort and Mergesort will always compare neighboring elements. Only time two elements are not compared, is when the algorithm knows there is an element in between. I think the same holds for most other O(nlog n) sorting algorithms.

0

I suspect not. Consider a group of values consisting entirely of duplicates of one value. These are partitioned into 2 groups A and B such that no value in group A is greater than any value in group B. These are then sorted within themselves. The value end of A and the beginning of B need not have been compared.

I don't know if there are any practical example of this, but it's fun to think about.

0

For this sort of problem (much like the more general comparison-sorting-is-n-log-n approach) a (mini) "adversary" argument would be effective -- try to break any algorithm which, on some input, does not make such a comparison.

The idea is very similar to the more general "comparison sorts require O(n log n) comparisons" proof, so I'd imagine you've either seen that recently or are about to cover it in your class.

0

because of my english, sorry.. i'm not influent at English.

@see Animated Sorting Algorithms : http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/all.html

this site show comparison of 8 soring algorithms: Insertion · Selection · Bubble · Shell · Merge · Heap · Quick · Quick3

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.