Editing Comb sort (section)

==Algorithm==
The basic idea is to eliminate ''turtles'', or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. ''Rabbits'', large values around the beginning of the list, do not pose a problem in bubble sort.

In bubble sort, when any two elements are compared, they always have a ''gap'' (distance from each other) of 1.<ref>{{cite web
   |website=[[National Institute of Standards and Technology]] (nist.gov)
   |url=https://xlinux.nist.gov/dads/HTML/combSort.html
   |title=comb sort
   |accessdate=March 9, 2021}}</ref> The basic idea of comb sort is that the gap can be much larger than 1. The inner loop of bubble sort, which does the actual ''swap'', is modified such that the gap between swapped elements goes down (for each iteration of outer loop) in steps of a "shrink factor" ''k'': {{math|[{{sfrac|''n''|''k''}}, {{sfrac|''n''|''k''<sup>2</sup>}}, {{sfrac|''n''|''k''<sup>3</sup>}}, ..., 1]}}.

The gap starts out as the length of the list ''n'' being sorted divided by the shrink factor ''k'' (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

The shrink factor has a great effect on the efficiency of comb sort. Dobosiewicz suggested ''k'' = 4/3 = 1.333…, while Lacey and Box suggest 1.3 as an ideal shrink factor after empirical testing on over 200,000 random lists of length approximately 1000. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with a gap of 1.

The pattern of repeated sorting passes with decreasing gaps is similar to Shellsort, but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap.  Comb sort's passes do not completely sort the elements.  This is the reason that [[Shellsort#Gap sequences|Shellsort gap sequences]] have a larger optimal shrink factor of about 2.25.

One additional refinement suggested by Lacey and Box is the "rule of 11": always use a gap size of 11, rounding up gap sizes of 9 or 10 (reached by dividing gaps of 12, 13 or 14 by 1.3) to 11.  This eliminates turtles surviving until the final gap-1 pass.

===Pseudocode===
 
 '''function''' combsort('''array''' input) '''is'''
 
     gap := input.size <span style="color:green">// Initialize gap size</span>
     shrink := 1.3 <span style="color:green">// Set the gap shrink factor</span>
     sorted := false
 
     '''loop while''' sorted = false
         <span style="color:green">// Update the gap value for a next comb</span>
         gap := floor(gap / shrink)
         '''if''' gap ≤ 1 '''then'''
             gap := 1
             sorted := true <span style="color:green">// If there are no swaps this pass, we are done</span>
         '''else if''' gap = 9 '''or''' gap = 10 '''then'''
             gap := 11      <span style="color:green">// The "rule of 11"</span>
         '''end if'''
 
         <span style="color:green">// A single "comb" over the input list</span>
         i := 0
         '''loop while''' i + gap < input.size<span style="color:green"> // See [[Shell sort]] for a similar idea</span>
             '''if''' input[i] > input[i+gap] '''then'''
                 [[Swap (computer science)|swap]](input[i], input[i+gap])
                 sorted := false
                 <span style="color:green">// If this assignment never happens within the loop,
                 // then there have been no swaps and the list is sorted.</span>
              '''end if'''
     
              i := i + 1
          '''end loop'''
      '''end loop'''
 '''end function'''
<!-- Please do not modify the pseudocode to make corrections unless you have verified, by translating the pseudocode to an actual programming language, that the corrections actually *are* corrections. Especially don't try to optimize it at the expense of clarity or understandability. -->