Shell Sort Minimum Comparisons

Question

What is the minimum number of comparisons needed by shell sort to sort a list of 8 items, given a gap list of 5,1?

I understand that the best case performance is an n(log(n)) case, but I can't work through the maths to get the full expression needed to put the given numbers in to get the minimum number of comparisons.

Answer 1

No, one speaks of asymtotic time when the number of elements is arbitrary big therefore n. When you have a exact number of elements, their number is constant. Therefore it is O(1).

Only in general it is BC O(n log n) for processing "n" elements. However, one is usually more interested in WC.

Here you need to work it out either by hand or write a simple program calculating them.

From the pseudocode:

# Sort an array a[0...7].
gaps = [5, 1]
foreach (gap in gaps) {
    for (i = gap; i < n; i += 1) {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
            a[j] = a[j - gap]

            a[j] = temp
    }
}

Plugging in the numbers is now straightforward.

Just for the sake of doing it, since you don't know the values of the elements you can only look it at WC. From the code above for the gap 5 we have 5,6,7 then the inner loop is also executed once for each of them, because of j = i; j >= gap; j -= gap. For gap 1 you have 1..7 in the outer for-loop and then you decrease for every execution (WC!) with 1. All in all you have:

gap(5) + gap(1) = (1 + 1 + 1) + (1 + 2 + 3 + 4 + 5 + 6 + 7) = 31