Do I need to compare sorting with all neighboring cells?

Question

Do I need to compare sorting by the largest value of A [i] and A [i + 1]? I think any sorting sort should, but I'm not sure. I checked the merge, insertion sorting and quicksort, and in each of them you need to compare the largest values ​​of A [i] and A [i + 1].

Answer 1

Each correct algorithm must compare neighboring cells if they are not equal. Evidence. Assume otherwise. A [i] and A [i + 1] in the final array were not compared (A [i] <A [i + 1). What happens if their positions are replaced by the original array? All comparisons made by the algorithm give the same results as in the original run (*), therefore it performs the same permutation, therefore their end positions are swapped, which makes the algorithm incorrect.

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

Answer 2

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

Answer 3

, , . , , . - .

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

, .

Answer 4

Shell . (, , ).

Answer 5

Quicksort Mergesort . , , . , O (nlog n).

Answer 6

, . , . 2 A B, A , B. . A B .

, - , .

Answer 7

( --n-log-n) "" () - , , .

The idea is very similar to the more general "sort collations that require O (n log n) comparisons," so I would suggest that you either saw this recently or are going to cover it in your class.

Answer 8

because of my english, sorry .. i don't influence english.

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

This site shows a comparison of 8 search algorithms: Insert · Select · Bubble · Shell · Merge · Heap · Fast · Quick3