When does shell sort make redundant comparisons?

My answer was:

Shell sort makes redundant comparison because if during comparison for elements far apart (when h is around 8), it compare two elements that are going to be neighbor, then is going to compare the same element again when during comparison for element near each other (when h is around 1). For开发者_如何学Python example if the list is 113 400 818 612 112 311 412 429, when h = 4, it will compare 113 and 112, and when h = 1, it will compare 113 and 112 again since it will compare elements that are closest to each other.

Is my answer correct?

---

Your example is definitely one where redundancy happens. In fact, redundancy cannot be avoided in Shell Sort. As you noticed, when h = 1, it always compares something that has been compared in previous preprocesses. One thing you can do to improve the performance of Shell Sort (i.e., reduce redundant comparisons) is choose h's smartly. For example, if you choose h to be 4, 2, 1, then 113 and 112 have to be compared three times while if you choose h to be 5, 3, 1, the redundant comparisons are significantly reduced. The general rule for picking h's is don't pick powers of 2 and don't pick multiples of one another. Hope this helps.