Sorting algorithms/Comb sort

You are encouraged to solve this task according to the task description, using any language you may know.

Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Task

Implement a   comb sort.



The Comb Sort is a variant of the Bubble Sort.

Like the Shell sort, the Comb Sort increases the gap used in comparisons and exchanges.

Dividing the gap by   



(
1
−

e

−
φ



)

−
1


≈
1.247330950103979


{\displaystyle (1-e^{-\varphi })^{-1}\approx 1.247330950103979}

    works best, but    1.3   may be more practical.



Some implementations use the insertion sort once the gap is less than a certain amount.



Also see

   the Wikipedia article:   Comb sort.


Variants:

 Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings.
 Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small).   Comb sort with a low gap isn't much better than the Bubble Sort.


Pseudocode:

function combsort(array input)
    gap := input.size //initialize gap size
    loop until gap = 1 and swaps = 0
        //update the gap value for a next comb. Below is an example
        gap := int(gap / 1.25)
        if gap < 1
          //minimum gap is 1
          gap := 1
        end if
        i := 0
        swaps := 0 //see Bubble Sort for an explanation
        //a single "comb" over the input list
        loop until i + gap >= input.size //see Shell sort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swaps := 1 // Flag a swap has occurred, so the
                           // list is not guaranteed sorted
            end if
            i := i + 1
        end loop
    end loop
end function



100 PROGRAM "CombSrt.bas"
110 RANDOMIZE
120 NUMERIC ARRAY(11 TO 30)
130 CALL INIT(ARRAY)
140 CALL WRITE(ARRAY)
150 CALL COMBSORT(ARRAY)
160 CALL WRITE(ARRAY)
170 DEF INIT(REF A)
180   FOR I=LBOUND(A) TO UBOUND(A)
190     LET A(I)=RND(98)+1
200   NEXT
210 END DEF
220 DEF WRITE(REF A)
230   FOR I=LBOUND(A) TO UBOUND(A)
240     PRINT A(I);
250   NEXT
260   PRINT
270 END DEF
280 DEF COMBSORT(REF A)
290   LET N,GAP=UBOUND(A):LET SW=1
300   DO WHILE GAP>1 OR SW
310     LET GAP=MAX(INT(GAP/1.3),1):LET SW=0
320     FOR I=LBOUND(A) TO N-GAP
330       IF A(I)>A(I+GAP) THEN
340         LET T=A(I):LET A(I)=A(I+GAP):LET A(I+GAP)=T
350         LET SW=1
360       END IF
370     NEXT
380   LOOP
390 END DEF