CODEWITHSUNDEEP
algorithmsortingproofcorrectness
ihake
ihake

Reputation: 1841

Has Comb Sort been proven correct? Can it be?

I've been doing some research on Comb Sort and I'm trying to figure out whether the algorithm has been proven correct. However, I can't seem to find a great deal of documentation on the algorithm. It's a very simple algorithm, though--basically a variant of Bubble Sort--and I'm guessing the proof isn't complicated. Does anyone have ideas about where I can find more info on this, or thoughts about how to prove it from scratch?

For those unfamiliar with Comb Sort, you can find the pseudo code on the Wikipedia article.

Upvotes: 1

Views: 622

Answers (1)

kaya3
kaya3

Reputation: 51152

Let's use the pseudocode from Wikipedia:

function combsort(array input) is
    gap := input.size
    shrink := 1.3
    sorted := false

    loop while sorted = false
        gap := floor(gap / shrink)
        if gap ≤ 1 then
            gap := 1
            sorted := true
        end if

        i := 0
        loop while i + gap < input.size
            if input[i] > input[i+gap] then
                swap(input[i], input[i+gap])
                sorted := false
            end if

            i := i + 1
         end loop
     end loop
end function

The main loop is while sorted = false, and there no break statements stopping the loop early, which is very helpful for the proof: if this loop ever terminates, it must be the case that sorted = true. So really, we only have to show two things: firstly that the loop does terminate, and secondly that if sorted = true at the end of the loop then the array actually is sorted.

  • The loop terminates because each time sorted is still false at the end of an iteration, either gap gets smaller, or gap stays the same and the number of inversions in the array gets smaller. Both gap and the number of inversions are integers bounded below by 1 and 0 respectively, so they cannot get smaller indefinitely.
    • If gap was 2 or more, then it gets smaller on that iteration (note the floor function).
    • If gap was 1, then it stayed at 1, and sorted was set to true before the inner loop. sorted can only be set back to false by swapping input[i] and input[i+1] for some i where input[i] > input[i+1]. Such a swap reduces the number of inversions in the array by 1. The inner loop does not perform swaps in any other circumstances, so no swap can increase the number of inversions when gap = 1.
  • If sorted = true at the end of the loop, we know that gap = 1 because otherwise sorted cannot be set to true. Then we also know that every input[i] <= input[i+1] because if this were not true for some i, then sorted would have been set to false. Therefore, sorted is only true at the end of the loop when every pair of adjacent elements in the array is in order, i.e. the array is sorted.

Upvotes: 0

Related Questions