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



' version 21-10-2016
' compile with: fbc -s console
' for boundary checks on array's compile with: fbc -s console -exx
 
Sub compsort(bs() As Long)
    ' sort from lower bound to the highter bound
    ' array's can have subscript range from -2147483648 to +2147483647
    Dim As Long lb = LBound(bs)
    Dim As Long ub = UBound(bs)
    Dim As Long gap = ub - lb
    Dim As Long done, i
 
    Do
        gap = Int (gap / 1.3)
        If gap < 1 Then gap = 1
        done = 0
        For i = lb To ub - gap
            If bs(i) > bs(i + gap) Then
                Swap bs(i), bs(i + gap)
                done = 1
            End If
        Next
    Loop Until ((gap = 1) And (done = 0))
 
End Sub
 
Sub comp11sort(bs() As Long)
    ' sort from lower bound to the higher bound
    ' array's can have subscript range from -2147483648 to +2147483647
    Dim As Long lb = LBound(bs)
    Dim As Long ub = UBound(bs)
    Dim As Long gap = ub - lb
    Dim As Long done, i
 
    Do
        gap = Int(gap / 1.24733)
        If gap = 9 Or gap = 10 Then
            gap = 11
        ElseIf gap < 1 Then
            gap = 1
        End If
        done = 0
        For i = lb To ub - gap
            If bs(i) > bs(i + gap) Then
                Swap bs(i), bs(i + gap)
                done = 1
            End If
        Next
    Loop Until ((gap = 1) And (done = 0))
 
End Sub
 
' ------=< MAIN >=------
 
Dim As Long i, array(-7 To 7)
 
Dim As Long a = LBound(array), b = UBound(array)
 
Randomize Timer
For i = a To b : array(i) = i  : Next
For i = a To b ' little shuffle
    Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
 
Print "normal comb sort"
Print "unsorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
compsort(array())  ' sort the array
Print "  sorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
 
Print
Print "comb11 sort"
For i = a To b ' little shuffle
    Swap array(i), array(Int(Rnd * (b - a +1)) + a)
Next
Print "unsorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
comp11sort(array())  ' sort the array
Print "  sorted ";
For i = a To b : Print Using "####"; array(i); : Next : Print
 
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End