comparison sort problem

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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