Sorting algorithms/Comb sort: Difference between revisions

Content added Content deleted

Inline

Revision as of 03:42, 2 March 2016

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

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^{-\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. See the article on Wikipedia. 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

ActionScript

<lang ActionScript>function combSort(input:Array) { var gap:uint = input.length; var swapped:Boolean = false; while(gap > 1 || swapped) { gap /= 1.25; swapped = false; for(var i:uint = 0; i + gap < input.length; i++) { if(input[i] > input[i+gap]) { var tmp = input[i]; input[i] = input[i+gap]; input[i+gap]=tmp; swapped = true; } } } return input; }</lang>

Ada

<lang Ada>with Ada.Text_IO; procedure Comb_Sort is

  generic
     type Element_Type is private;
     type Index_Type is range <>;
     type Array_Type is array (Index_Type range <>) of Element_Type;
     with function ">" (Left, Right : Element_Type) return Boolean is <>;
     with function "+" (Left : Index_Type; Right : Natural) return Index_Type is <>;
     with function "-" (Left : Index_Type; Right : Natural) return Index_Type is <>;
  procedure Comb_Sort (Data: in out Array_Type);

  procedure Comb_Sort (Data: in out Array_Type) is
     procedure Swap (Left, Right : in Index_Type) is
        Temp : Element_Type := Data(Left);
     begin
        Data(Left)  := Data(Right);
        Data(Right) := Temp;
     end Swap;
     Gap : Natural := Data'Length;
     Swap_Occured : Boolean;
  begin
     loop
        Gap := Natural (Float(Gap) / 1.25 - 0.5);
        if Gap < 1 then
           Gap := 1;
        end if;
        Swap_Occured := False;
        for I in Data'First .. Data'Last - Gap loop
           if Data (I) > Data (I+Gap) then
              Swap (I, I+Gap);
              Swap_Occured := True;
           end if;
        end loop;
        exit when Gap = 1 and not Swap_Occured;
     end loop;
  end Comb_Sort;

  type Integer_Array is array (Positive range <>) of Integer;
  procedure Int_Comb_Sort is new Comb_Sort (Integer, Positive, Integer_Array);
  Test_Array : Integer_Array := (1, 3, 256, 0, 3, 4, -1);

begin

  Int_Comb_Sort (Test_Array);
  for I in Test_Array'Range loop
     Ada.Text_IO.Put (Integer'Image (Test_Array (I)));
  end loop;
  Ada.Text_IO.New_Line;

end Comb_Sort;</lang>

Output:

-1 0 1 3 3 4 256

AutoHotkey

<lang autohotkey>List1 = 23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78 List2 = 88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70

List2Array(List1, "MyArray") CombSort("MyArray") MsgBox, % List1 "`n" Array2List("MyArray")

List2Array(List2, "MyArray") CombSort("MyArray") MsgBox, % List2 "`n" Array2List("MyArray")

---------------------------------------------------------------------------

CombSort(Array) { ; CombSort of Array %Array%, length = %Array%0

---------------------------------------------------------------------------

   Gap := %Array%0
   While Gap > 1 Or Swaps {
       If (Gap > 1)
           Gap := 4 * Gap // 5
       i := Swaps := False
       While (j := ++i + Gap) <= %Array%0 {
           If (%Array%%i% > %Array%%j%) {
               Swaps := True
               %Array%%i% := (%Array%%j% "", %Array%%j% := %Array%%i%)
           }
       }
   }

}

---------------------------------------------------------------------------

List2Array(List, Array) { ; creates an array from a comma separated list

---------------------------------------------------------------------------

   global
   StringSplit, %Array%, List, `,

}

---------------------------------------------------------------------------

Array2List(Array) { ; returns a comma separated list from an array

---------------------------------------------------------------------------

   Loop, % %Array%0
       List .= (A_Index = 1 ? "" : ",") %Array%%A_Index%
   Return, List

}</lang> Message (1) box shows:

23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78
12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99

Message (2) box shows:

88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70
0,4,5,8,14,18,20,31,33,44,62,70,73,75,76,78,81,82,84,88

AWK

<lang awk>function combsort( a, len, gap, igap, swap, swaps, i ) { gap = len swaps = 1

while( gap > 1 || swaps ) { gap /= 1.2473; if ( gap < 1 ) gap = 1 i = swaps = 0 while( i + gap < len ) { igap = i + int(gap) if ( a[i] > a[igap] ) { swap = a[i] a[i] = a[igap] a[igap] = swap swaps = 1 } i++; } } }

BEGIN { a[0] = 5 a[1] = 2 a[2] = 7 a[3] = -11 a[4] = 6 a[5] = 1

combsort( a, length(a) )

for( i=0; i<length(a); i++ ) print a[i] }</lang>

BBC BASIC

<lang BBC BASIC>DEF PROC_CombSort11(Size%)

gap%=Size% REPEAT

 IF gap% > 1 THEN
    gap%=gap% / 1.3
    IF gap%=9 OR gap%=10 gap%=11
 ENDIF
 I% = 1
 Finished%=TRUE
 REPEAT
   IF data%(I%) > data%(I%+gap%) THEN
      SWAP data%(I%),data%(I%+gap%)
      Finished% = FALSE
   ENDIF
   I%+=1
 UNTIL I%+gap% > Size%

UNTIL gap%=1 AND Finished%

ENDPROC</lang>

C

Implementation of Combsort11. Its efficiency can be improved by just switching to Insertion sort when the gap size becomes less than 10. <lang c>void Combsort11(double a[], int nElements) {

 int i, j, gap, swapped = 1;
 double temp;

 gap = nElements;
 while (gap > 1 || swapped == 1)
 {
   gap = gap * 10 / 13;
   if (gap == 9 || gap == 10) gap = 11;
   if (gap < 1) gap = 1;
   swapped = 0;
   for (i = 0, j = gap; j < nElements; i++, j++)
   {
     if (a[i] > a[j])
     {
       temp = a[i];
       a[i] = a[j];
       a[j] = temp;
       swapped = 1;
     }
   }
 }

}</lang>

C++

This is copied from the Wikipedia article. <lang cpp>template<class ForwardIterator> void combsort ( ForwardIterator first, ForwardIterator last ) {

   static const double shrink_factor = 1.247330950103979;
   typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
   difference_type gap = std::distance(first, last);
   bool swaps = true;

   while ( (gap > 1) || (swaps == true) ){
       if (gap > 1)
           gap = static_cast<difference_type>(gap/shrink_factor);

       swaps = false;
       ForwardIterator itLeft(first);
       ForwardIterator itRight(first); std::advance(itRight, gap);

       for ( ; itRight!=last; ++itLeft, ++itRight ){
           if ( (*itRight) < (*itLeft) ){
               std::iter_swap(itLeft, itRight);
               swaps = true;
           }
       }
   }

}</lang>

C#

<lang csharp>using System;

namespace CombSort {

   class Program
   {
       static void Main(string[] args)
       {
           int[] unsorted = new int[] { 3, 5, 1, 9, 7, 6, 8, 2, 4 };
           Console.WriteLine(string.Join(",", combSort(unsorted)));
       }
       public static int[] combSort(int[] input)
       {
           double gap = input.Length;
           bool swaps = true;
           while (gap > 1 || swaps)
           {
               gap /= 1.247330950103979;
               if (gap < 1) { gap = 1; }
               int i = 0;
               swaps = false;
               while (i + gap < input.Length)
               {
                   int igap = i + (int)gap;
                   if (input[i] > input[igap])
                   {
                       int swap = input[i];
                       input[i] = input[igap];
                       input[igap] = swap;
                       swaps = true;
                   }
                   i++;
               }
           }
           return input;
       }
   }

}</lang>

COBOL

This excerpt contains just enough of the procedure division to show the workings. See the example for the bubble sort for a more complete program. <lang COBOL> C-PROCESS SECTION.

      C-000.
          DISPLAY "SORT STARTING".

          MOVE WC-SIZE TO WC-GAP.

          PERFORM E-COMB UNTIL WC-GAP = 1 AND FINISHED.

          DISPLAY "SORT FINISHED".

      C-999.
          EXIT.

      E-COMB SECTION.
      E-000.
          IF WC-GAP > 1
             DIVIDE WC-GAP BY 1.3 GIVING WC-GAP
             IF WC-GAP = 9 OR 10
                MOVE 11 TO WC-GAP.

          MOVE 1   TO WC-SUB-1.
          MOVE "Y" TO WF-FINISHED.

          PERFORM F-SCAN UNTIL WC-SUB-1 + WC-GAP > WC-SIZE.

      E-999.
          EXIT.

      F-SCAN SECTION.
      F-000.
          ADD WC-SUB-1 WC-GAP GIVING WC-SUB-2.
          IF WB-ENTRY(WC-SUB-1) > WB-ENTRY(WC-SUB-2)
             MOVE WB-ENTRY(WC-SUB-1) TO WC-TEMP
             MOVE WB-ENTRY(WC-SUB-2) TO WB-ENTRY(WC-SUB-1)
             MOVE WC-TEMP            TO WB-ENTRY(WC-SUB-2)
             MOVE "N"                TO WF-FINISHED.

          ADD 1 TO WC-SUB-1.

      F-999.
          EXIT.</lang>

D

Translation of: Python

<lang d>import std.stdio, std.algorithm;

void combSort(T)(T[] input) pure nothrow @safe @nogc {

   int gap = input.length;
   bool swaps = true;

   while (gap > 1 || swaps) {
       gap = max(1, cast(int)(gap / 1.2473));
       swaps = false;
       foreach (immutable i; 0 .. input.length - gap)
           if (input[i] > input[i + gap]) {
               input[i].swap(input[i + gap]);
               swaps = true;
           }
   }

}

void main() {

   auto data = [28, 44, 46, 24, 19, 2, 17, 11, 25, 4];
   data.combSort;
   data.writeln;

}</lang>

Output:

[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

Eiffel

class COMB_SORT [G -> COMPARABLE]

feature

combsort (ar: ARRAY [G]): ARRAY [G] -- Sorted array in ascending order. require array_not_void: ar /= Void local gap, i: INTEGER swap: G swapped: BOOLEAN shrink: REAL_64 do create Result.make_empty Result.deep_copy (ar) gap := Result.count from until gap = 1 and swapped = False loop from i := Result.lower swapped := False until i + gap > Result.count loop if Result [i] > Result [i + gap] then swap := Result [i] Result [i] := Result [i + gap] Result [i + gap] := swap swapped := True end i := i + 1 end shrink := gap / 1.3 gap := shrink.floor if gap < 1 then gap := 1 end end ensure Result_is_set: Result /= Void Result_is_sorted: is_sorted (Result) end

feature {NONE}

is_sorted (ar: ARRAY [G]): BOOLEAN --- Is 'ar' sorted in ascending order? require ar_not_empty: ar.is_empty = False local i: INTEGER do Result := True from i := ar.lower until i = ar.upper loop if ar [i] > ar [i + 1] then Result := False end i := i + 1 end end

end

</lang> Test: <lang Eiffel> class APPLICATION

create make

feature

make do test := <<1, 5, 99, 2, 95, 7, -7>> io.put_string ("unsorted" + "%N") across test as ar loop io.put_string (ar.item.out + "%T") end io.put_string ("%N" + "sorted:" + "%N") create combsort test := combsort.combsort (test) across test as ar loop io.put_string (ar.item.out + "%T") end end

combsort: COMB_SORT [INTEGER]

test: ARRAY [INTEGER]

end </lang>

Output:

unsorted:
1 5 99 2 95 7 -7
sorted:
-7 1 2 5 7 95 99

Forth

This is an implementation of Comb sort with a different ending. Here Gnome sort is used, since it is rather small. The dataset is rather large, because otherwise the Comb sort routine would never kick in, passing control to Gnome sort almost right away. Note Comb sort can be kept much simpler this way, because Combsort11 optimizations and swapped flags can be discarded. <lang forth>defer precedes defer exchange

gnomesort ( a n)

 swap >r 1                            ( n c)
 begin                                ( n c)
   over over >                        ( n c f)
 while                                ( n c)
   dup if                             ( n c)
     dup dup 1- over over r@ precedes
     if r@ exchange 1- else drop drop 1+ then
   else 1+ then                       ( n c)
 repeat drop drop r> drop             ( --)

combsort ( a n --)

 dup begin                            ( a n g)
   10 13 */ tuck >r >r 0              ( a g 0)
   begin                              ( a g 0)
     over r@ <                        ( a g 0 f)
   while                              ( a g 0)
     rot >r over over r@ precedes     ( g 0 f)
     if over over r@ exchange then    ( g 0)
     r> rot 1+ rot 1+                 ( a g 0)
   repeat drop drop r> r>             ( a n g)
   dup 9 <                            ( a n g f)
 until drop gnomesort                 ( --)

create example

 8 93 69 52 50 79 33 52 19 77 , , , , , , , , , ,
72 85 11 61 64 80 64 76 47 65 , , , , , , , , , ,
 13 47 23 40 87 45 2 48 22 69 , , , , , , , , , ,
 1 53 33 60 57 14 76 32 59 12 , , , , , , , , , ,
74 38 39 22 87 28 37 93 71 88 , , , , , , , , , ,
56 35 48 99 21 35 26 28 58 85 , , , , , , , , , ,
27 16 54 88 82 18 45 64 45 87 , , , , , , , , , ,
  98 97 60 77 43 1 64 0 32 89 , , , , , , , , , ,
 77 90 68 83 9 76 10 10 95 12 , , , , , , , , , ,
  99 23 74 58 54 25 50 9 94 1 , , , , , , , , , ,

noname >r cells r@ + @ swap cells r> + @ swap < ; is precedes

noname >r cells r@ + swap cells r> + over @ over @ swap rot ! swap ! ; is exchange

.array 100 0 do example i cells + ? loop cr ;

.array example 100 combsort .array</lang>

Fortran

Works with: Fortran version 90 and later

<lang fortran>program Combsort_Demo

 implicit none

 integer, parameter :: num = 20
 real :: array(num)

 call random_seed
 call random_number(array)
 write(*,*) "Unsorted array:-"
 write(*,*) array
 write(*,*)
 call combsort(array)
 write(*,*) "Sorted array:-"
 write(*,*) array

contains

 subroutine combsort(a)

   real, intent(in out) :: a(:)
   real :: temp
   integer :: i, gap
   logical :: swapped = .true.

   gap = size(a)
   do while (gap > 1 .or. swapped)
     gap = gap / 1.3
     if (gap < 1) gap = 1
     swapped = .false.
     do i = 1, size(a)-gap
       if (a(i) > a(i+gap)) then
         temp = a(i)
         a(i) = a(i+gap)
         a(i+gap) = temp;
         swapped = .true.
       end if
     end do
   end do

 end subroutine combsort

end program Combsort_Demo</lang>

FreeBASIC

<lang FreeBASIC>' version 05-07-2015 ' compile with: fbc -s console ' for boundry checks on array's compile with: fbc -s console -exx

Sub compsort(bs() As Integer)

   ' sort from lower bound to the highter bound
   ' array's can have subscript range from -2147483648 to +2147483647
   Dim As Integer lb = LBound(bs)
   Dim As Integer ub = UBound(bs)
   Dim As Integer gap = ub - lb
   Dim As Integer 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

' ------=< MAIN >=------

Dim As Integer i, array(-7 To 8)

Dim As Integer a = LBound(array), b = UBound(array) -1

Randomize Timer For i = a To b : array(i) = i : Next For i = a To b ' little shuffle

   Swap array(i), array(Rnd * (b - a) + a)

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

' empty keyboard buffer While Inkey <> "" : Var _key_ = Inkey : Wend Print : Print "hit any key to end program" Sleep End</lang>

Output:

normal comb sort
unsorted   -1   3  -4  -6  -7   2   7  -3   1   4   0  -5  -2   5   6   0
  sorted   -7  -6  -5  -4  -3  -2  -1   0   0   1   2   3   4   5   6   7

Go

<lang go>package main

import "fmt"

func main() {

   a := []int{170, 45, 75, -90, -802, 24, 2, 66}
   fmt.Println("before:", a)
   combSort(a)
   fmt.Println("after: ", a)

}

func combSort(a []int) {

   if len(a) < 2 {
       return
   }
   for gap := len(a); ; {
       if gap > 1 {
           gap = gap * 4 / 5
       }
       swapped := false
       for i := 0; ; {
           if a[i] > a[i+gap] {
               a[i], a[i+gap] = a[i+gap], a[i]
               swapped = true
           }
           i++
           if i+gap >= len(a) {
               break
           }
       }
       if gap == 1 && !swapped {
           break
       }
   }

}</lang>

More generic version that sorts anything that implements sort.Interface: <lang go>package main

import (

 "sort"
 "fmt"

)

func main() {

   a := []int{170, 45, 75, -90, -802, 24, 2, 66}
   fmt.Println("before:", a)
   combSort(sort.IntSlice(a))
   fmt.Println("after: ", a)

}

func combSort(a sort.Interface) {

   if a.Len() < 2 {
       return
   }
   for gap := a.Len(); ; {
       if gap > 1 {
           gap = gap * 4 / 5
       }
       swapped := false
       for i := 0; ; {
           if a.Less(i+gap, i) {
               a.Swap(i, i+gap)
               swapped = true
           }
           i++
           if i+gap >= a.Len() {
               break
           }
       }
       if gap == 1 && !swapped {
           break
       }
   }

}</lang>

Groovy

Combsort solution: <lang groovy>def makeSwap = { a, i, j -> print "."; a[i] ^= a[j]; a[j] ^= a[i]; a[i] ^= a[j] }

def checkSwap = { a, i, j -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }

def combSort = { input ->

   def swap = checkSwap.curry(input)
   def size = input.size()
   def gap = size
   def swapped = true
   while (gap != 1 || swapped) {
       gap = (gap / 1.247330950103979) as int
       gap = (gap < 1) ? 1 : gap
       swapped = (0..<(size-gap)).any { swap(it, it + gap) }
   }
   input

}</lang>

Combsort11 solution: <lang groovy>def combSort11 = { input ->

   def swap = checkSwap.curry(input)
   def size = input.size()
   def gap = size
   def swapped = true
   while (gap != 1 || swapped) {
       gap = (gap / 1.247330950103979) as int
       gap = ((gap < 1) ? 1 : ([10,9].contains(gap) ? 11 : gap))
       swapped = (0..<(size-gap)).any { swap(it, it + gap) }
   }
   input

}</lang>

Test: <lang groovy>println (combSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])) println (combSort11([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])) println () println (combSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])) println (combSort11([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</lang>

Output:

..................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
..........................................................................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

...............................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
...............................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]

Haskell

<lang haskell>import Data.List import Control.Arrow import Control.Monad

flgInsert x xs = ((x:xs==) &&& id)$ insert x xs

gapSwapping k = (and *** concat. transpose). unzip

 . map (foldr (\x (b,xs) -> first (b &&)$ flgInsert x xs) (True,[]))
 . transpose. takeWhile (not.null). unfoldr (Just. splitAt k)

combSort xs = (snd. fst) $ until (\((b,_),g)-> b && g==1)

   (\((_,xs),g) ->(gapSwapping g xs, fg g)) ((False,xs), fg $ length xs)
 where fg = max 1. truncate. (/1.25). fromIntegral</lang>

Example: <lang haskell>*Main> combSort [23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78] [12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99]</lang>

Io

<lang io>List do(

   combSortInPlace := method(
       gap := size
       swap := true

       while(gap > 1 or swap,
           swap = false
           gap = (gap / 1.25) floor

           for(i, 0, size - gap,
               if(at(i) > at(i + gap),
                   swap = true
                   swapIndices(i, i + gap)
               )
           )
       )
   self)

)

lst := list(23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78) lst combSortInPlace println # ==> list(12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99)</lang>

Icon and Unicon

<lang Icon>procedure main() #: demonstrate various ways to sort a list and string

  demosort(combsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

procedure combsort(X,op) #: return sorted X local gap,swapped,i

  op := sortop(op,X)                     # select how and what we sort

  swappped := gap := *X                  # initialize gap size and say swapped
  until /swapped & gap = 1 do {
     gap := integer(gap / 1.25)          # update the gap value for a next comb
     gap <:= 1                           # minimum gap of 1
     swapped := &null

      i := 0
      until (i +:= 1) + gap > *X do      # a single "comb" over the input list
        if op(X[i+gap],X[i]) then 
           X[i+1] :=: X[swapped := i]    # swap and flag as unsorted
     }
  return X

end</lang>

Note: This example relies on the supporting procedures 'sortop', and 'demosort' in Bubble Sort. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

Abbreviated sample output:

Sorting Demo using procedure combsort
  on list : [ 3 14 1 5 9 2 6 3 ]
    with op = &null:         [ 1 2 3 3 5 6 9 14 ]   (0 ms)
  ...
  on string : "qwerty"
    with op = &null:         "eqrtwy"   (0 ms)

J

Generally, this task should be accomplished in J using /:~. Here we take an approach that's more comparable with the other examples on this page.

Large gap sizes allow some parallelism in comparisons and swaps. (If the gap size is G, then G pairs can be compared and swapped in parallel.) Beyond that, however, the data flow complexity of this algorithm requires a fair bit of micro-management.

<lang J>combSort=:3 :0

 gap=. #y
 whilst.1 < gap+swaps do.
   swaps=. 0
   i=. i.2,gap=. 1 >. <.gap%1.25
   while.{:$i=.i #"1~ ({: i) < #y do.
     swaps=.swaps+#{:k=.i #"1~b=. >/ i{y
     i=. i+gap
     y=.((|.k){y) k} y
   end.
 end.
 y

)</lang>

Example use:

   combSort 23 76 99 58 97 57 35 89 51 38 95 92 24 46 31 24 14 12 57 78
12 14 23 24 24 31 35 38 46 51 57 57 58 76 78 89 92 95 97 99
   combSort 88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70
0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88

Java

This is copied from the Wikipedia article. <lang java>public static <E extends Comparable<? super E>> void sort(E[] input) {

   int gap = input.length;
   boolean swapped = true;
   while (gap > 1 || swapped) {
       if (gap > 1) {
           gap = (int) (gap / 1.3);
       }
       swapped = false;
       for (int i = 0; i + gap < input.length; i++) {
           if (input[i].compareTo(input[i + gap]) > 0) {
               E t = input[i];
               input[i] = input[i + gap];
               input[i + gap] = t;
               swapped = true;
           }
       }
   }

}</lang>

JavaScript

 // Node 5.4.1 tested implementation (ES6)
 function is_array_sorted(arr) {
     var sorted = true;
     for (var i = 0; i < arr.length - 1; i++) {
         if (arr[i] > arr[i + 1]) {
             sorted = false;
             break;
         }
     }
     return sorted;
 }

 // Array to sort
 var arr = [4, 9, 0, 3, 1, 5];

 var iteration_count = 0;
 var gap = arr.length - 2;
 var decrease_factor = 1.25;

 // Until array is not sorted, repeat iterations
 while (!is_array_sorted(arr)) {
     // If not first gap
     if (iteration_count > 0)
     // Calculate gap
         gap = (gap == 1) ? gap : Math.floor(gap / decrease_factor);

     // Set front and back elements and increment to a gap
     var front = 0;
     var back = gap;
     while (back <= arr.length - 1) {
         // If elements are not ordered swap them
         if (arr[front] > arr[back]) {
             var temp = arr[front];
             arr[front] = arr[back];
             arr[back] = temp;
         }

         // Increment and re-run swapping
         front += 1;
         back += 1;
     }
     iteration_count += 1;
 }

 // Print the sorted array
 console.log(arr);

}</lang>

Output:

 [0, 1, 3, 4, 5, 9]

jq

Works with: jq version 1.4

An implementation of the pseudo-code in the task description: <lang jq># Input should be the array to be sorted. def combsort:

 # As soon as "condition" is true, emit . and stop:
 def do_until(condition; next):
   def u: if condition then . else (next|u) end;
 u;

 def swap(i;j):
   if i==j then . else .[i] as $tmp | .[i] = .[j] | .[j] = $tmp end;

  . as $in
 | length as $length
   # state: [gap, swaps, array] where:
   #   gap is the gap size;
   #   swaps is a boolean flag indicating a swap has occurred,
   #         implying that the array might not be sorted;
   #   array is the current state of the array being sorted
 | [ $length, false, $in ] 
 | do_until( .[0] == 1 and .[1] == false;
     # update the gap value for the next "comb":
     ([1, ((.[0] / 1.25) | floor)] | max) as $gap   # minimum gap is 1

     # state: [i, swaps, array]
     | [0, false, .[2]]
     # a single "comb" over the input list:
     | do_until( (.[0] + $gap) >= $length;
         .[0] as $i
         | if .[2][$i] > .[2][$i+$gap] then
             [$i+1, true, (.[2]|swap($i; $i+$gap))]
           else .[0] += 1
           end)
     | .[0] = $gap )
 | .[2] ;</lang>

Liberty BASIC

<lang lb> 'randomize 0.5 itemCount = 20

   dim item(itemCount)
   for i = 1 to itemCount
       item(i) = int(rnd(1) * 100)
   next i
   print "Before Sort"
   for i = 1 to itemCount
       print item(i)
   next i
   print: print

't0=time$("ms")

   gap=itemCount
   while gap>1 or swaps <> 0
       gap=int(gap/1.25)
       'if gap = 10 or gap = 9 then gap = 11    'uncomment to get Combsort11
       if gap <1 then gap = 1
       i = 1
       swaps = 0
       for i = 1 to itemCount-gap
           if item(i) > item(i + gap) then
               temp = item(i)
               item(i) = item(i + gap)
               item(i + gap) = temp
               swaps = 1
           end if
       next
   wend

   print "After Sort"

't1=time$("ms") 'print t1-t0

   for i = 1 to itemCount
       print item(i)
   next i

end </lang>

Lua

<lang lua>function combsort(t)

 local gapd, gap, swaps = 1.2473, #t, 0
 while gap + swaps > 1 do
   local k = 0
   swaps = 0
   if gap > 1 then gap = math.floor(gap / gapd) end
   for k = 1, #t - gap do
     if t[k] > t[k + gap] then
       t[k], t[k + gap], swaps = t[k + gap], t[k], swaps + 1
     end
   end
 end
 return t

end

print(unpack(combsort{3,5,1,2,7,4,8,3,6,4,1}))</lang>

Mathematica

<lang Mathematica>combSort[list_] := Module[{ gap = 0, listSize = 0, swaps = True},

       gap = listSize = Length[list];
       While[ !((gap <= 1) && (swaps == False)),
   
           gap = Floor@Divide[gap, 1.25];
           If[ gap < 1, gap = 1]; i = 1; swaps = False;
           
           While[ ! ((i + gap - 1) >= listSize), 
               If[ listi > listi + gap, swaps = True;
               listi ;; i + gap = listi + gap ;; i ;; -1;  
               ];
           i++; 
           ]
       ]

]</lang>

combSort@{2, 1, 3, 7, 6}
->{1, 2, 3, 6, 7}

MATLAB / Octave

<lang MATLAB>function list = combSort(list)

   listSize = numel(list);
   gap = int32(listSize); %Coerce gap to an int so we can use the idivide function
   swaps = true; %Swap flag
   
   while not((gap <= 1) && (swaps == false))
       
       gap = idivide(gap,1.25,'floor'); %Int divide, floor the resulting operation
       
       if gap < 1
           gap = 1;
       end
       
       i = 1; %i equals 1 because all arrays are 1 based in MATLAB
       swaps = false;
       
       %i + gap must be subtracted by 1 because the pseudo-code was writen
       %for 0 based arrays
       while not((i + gap - 1) >= listSize)
           
           if (list(i) > list(i+gap))
               list([i i+gap]) = list([i+gap i]); %swap
               swaps = true;
           end
       i = i + 1;
       
       end %while      
   end %while

end %combSort</lang>

Sample Output: <lang MATLAB>>> combSort([4 3 1 5 6 2])

ans =

    1     2     3     4     5     6</lang>

MAXScript

<lang MAXScript>fn combSort arr = ( local gap = arr.count local swaps = 1 while not (gap == 1 and swaps == 0) do ( gap = (gap / 1.25) as integer if gap < 1 do ( gap = 1 ) local i = 1 swaps = 0 while not (i + gap > arr.count) do ( if arr[i] > arr[i+gap] do ( swap arr[i] arr[i+gap] swaps = 1 ) i += 1

)

) return arr )</lang> Output: <lang MAXScript> a = for i in 1 to 10 collect random 1 10

(2, 6, 5, 9, 10, 7, 2, 6, 1, 4)

combsort a

(1, 2, 2, 4, 5, 6, 6, 7, 9, 10)

</lang>

NetRexx

<lang NetRexx>/* NetRexx */

options replace format comments java crossref savelog symbols binary

placesList = [String -

   "UK  London",     "US  New York"   -
 , "US  Boston",     "US  Washington" -
 , "UK  Washington", "US  Birmingham" -
 , "UK  Birmingham", "UK  Boston"     -

] sortedList = combSort(String[] Arrays.copyOf(placesList, placesList.length))

lists = [placesList, sortedList] loop ln = 0 to lists.length - 1

 cl = lists[ln]
 loop ct = 0 to cl.length - 1
   say cl[ct]
   end ct
   say
 end ln

return

method combSort(input = String[]) public constant binary returns String[]

 swaps = isTrue
 gap = input.length
 loop label comb until gap = 1 & \swaps
   gap = int gap / 1.25
   if gap < 1 then
     gap = 1
   i_ = 0
   swaps = isFalse
   loop label swaps until i_ + gap >= input.length
     if input[i_].compareTo(input[i_ + gap]) > 0 then do
       swap            = input[i_]
       input[i_]       = input[i_ + gap]
       input[i_ + gap] = swap
       swaps           = isTrue
       end
       i_ = i_ + 1
     end swaps
   end comb

 return input

method isTrue public constant binary returns boolean

 return 1 == 1

method isFalse public constant binary returns boolean

 return \isTrue

</lang>

Output

UK  London
US  New York
US  Boston
US  Washington
UK  Washington
US  Birmingham
UK  Birmingham
UK  Boston

UK  Birmingham
UK  Boston
UK  London
UK  Washington
US  Birmingham
US  Boston
US  New York
US  Washington

Nim

<lang nim>proc combSort[T](a: var openarray[T]) =

 var gap = a.len
 var swapped = true
 while gap > 1 or swapped:
   gap = gap * 10 div 13
   if gap == 9 or gap == 10: gap = 11
   if gap < 1: gap = 1
   swapped = false
   var i = 0
   for j in gap .. <a.len:
     if a[i] > a[j]:
       swap a[i], a[j]
       swapped = true
     inc i

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782] combSort a echo a</lang> Output:

@[-31, 0, 2, 2, 4, 65, 83, 99, 782]

Objeck

<lang objeck> bundle Default {

 class Stooge {
   function : Main(args : String[]) ~ Nil {
     nums := [3, 5, 1, 9, 7, 6, 8, 2, 4];
     CombSort(nums);
     each(i : nums) {
       IO.Console->Print(nums[i])->Print(",");
     };
     IO.Console->PrintLine();
   }
  
   function : CombSort(input : Int[]) ~ Nil {
     gap : Float := input->Size();
     swaps := true;
     while(gap > 1 | swaps) {
       gap /= 1.247330950103979;
       if(gap < 1) { gap := 1; };
       i : Int := 0;
       swaps := false;
       while(i + gap < input->Size()) {
         igap : Int := i + gap->As(Int);
         if (input[i] > input[igap]) {
           swap : Int := input[i];
           input[i] := input[igap];
           input[igap] := swap;
           swaps := true;
         };          
         i += 1;
       };
     };
   }  
 }

} </lang>

OCaml

<lang ocaml>let comb_sort ~input =

 let input_length = Array.length input in
 let gap = ref(input_length) in
 let swapped = ref true in
 while (!gap > 1 || !swapped) do
   if (!gap > 1) then
     gap := int_of_float (float !gap /. 1.3);

   swapped := false;
   for i = 0 to input_length - !gap do
     if input.(i) > input.(i + !gap) then begin
       let tmp = input.(i) in
       input.(i) <- input.(i + !gap);
       input.(i + !gap) <- tmp;
       swapped := true;
     end
   done
 done

</lang>

Oz

<lang oz>declare

 proc {CombSort Arr}
    Low = {Array.low Arr}
    High = {Array.high Arr}
    Size = High - Low + 1
    Gap = {NewCell Size}
    Swapped = {NewCell true}
    proc {Swap I J}
       Arr.J := (Arr.I := Arr.J)
    end
 in
    for while:@Gap>1 orelse @Swapped do
       if @Gap > 1 then
          Gap := {Float.toInt {Floor {Int.toFloat @Gap} / 1.3}}
       end
       Swapped := false
       for I in Low..High-@Gap do
          if Arr.I > Arr.(I+@Gap) then
             {Swap I I+@Gap}
             Swapped := true
          end
       end
    end
 end
 Arr = {Tuple.toArray unit(3 1 4 1 5 9 2 6 5)}

in

 {CombSort Arr}
 {Show {Array.toRecord unit Arr}}</lang>

PARI/GP

<lang parigp>combSort(v)={

 my(phi=(1+sqrt(5))/2,magic=1/(1-exp(-phi)),g=#v,swaps);
 while(g>1 | swaps,
   if(g>1, g\=magic);
   swaps=0;
   for(i=1,#v-g,
     if(v[i]>v[i+g],
       my(t=v[i]);
       v[i]=v[i+g];
       v[i+g]=t;
       swaps++
     )
   )
 );
 v

};</lang>

Pascal

<lang pascal>program CombSortDemo;

type

 TIntArray = array[1..40] of integer;

var

 data: TIntArray;
 i: integer;

procedure combSort(var a: TIntArray);

 var
   i, gap, temp: integer;
   swapped: boolean;
 begin
   gap := length(a);
   swapped := true;
   while (gap > 1) or swapped do
   begin
     gap := trunc(gap / 1.3);
     if (gap < 1) then 
       gap := 1;
     swapped := false;
     for i := 1 to length(a) - gap do
       if a[i] > a[i+gap] then
       begin

temp := a[i];

         a[i] := a[i+gap];
         a[i+gap] := temp;
         swapped := true;
       end;
   end;
 end;

begin

 Randomize;
 writeln('The data before sorting:');
 for i := low(data) to high(data) do
 begin
   data[i] := Random(high(data));
   write(data[i]:4);
 end;
 writeln;
 combSort(data);
 writeln('The data after sorting:');
 for i := low(data) to high(data) do
 begin
   write(data[i]:4);
 end;
 writeln;

end.</lang> Output:

The data before sorting:
  10  26  32  10   9  32  38  37  12   9  16   7  25   1  37   7  24  22   7  36   2   5  10   5  33  35  32  18   5  28   7   5  36  12  16  36  24   3  29  15
The data after sorting:
   1   2   3   5   5   5   5   7   7   7   7   9   9  10  10  10  12  12  15  16  16  18  22  24  24  25  26  28  29  32  32  32  33  35  36  36  36  37  37  38

Perl

<lang perl>sub combSort {

   my @arr = @_;
   my $gap = @arr;
   my $swaps = 1;
   while ($gap > 1 || $swaps) {
       $gap /= 1.25 if $gap > 1;
       $swaps = 0;
       foreach my $i (0 .. $#arr - $gap) {
           if ($arr[$i] > $arr[$i+$gap]) {
               @arr[$i, $i+$gap] = @arr[$i+$gap, $i];
               $swaps = 1;
           }
       }
   }
   return @arr;

}</lang>

Perl 6

Translation of: Perl

<lang perl6>sub comb_sort ( @a is copy ) {

   my $gap = +@a;
   my $swaps = 1;
   while $gap > 1 or $swaps {
       $gap = ( ($gap * 4) div 5 ) || 1 if $gap > 1;

       $swaps = 0;
       for ^(+@a - $gap) -> $i {
           my $j = $i + $gap;
           if @a[$i] > @a[$j] {
               @a[$i, $j] .= reverse;
               $swaps = 1;
           }
       }
   }
   return @a;

}

my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) }; say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok'; </lang>

PHP

<lang php>function combSort($arr){ $gap = count($arr);

       $swap = true;

while ($gap > 1 || $swap){ if($gap > 1) $gap /= 1.25;

$swap = false; $i = 0; while($i+$gap < count($arr)){ if($arr[$i] > $arr[$i+$gap]){ list($arr[$i], $arr[$i+$gap]) = array($arr[$i+$gap],$arr[$i]); $swap = true; } $i++; } } return $arr; }</lang>

PicoLisp

<lang PicoLisp>(de combSort (Lst)

  (let (Gap (length Lst)  Swaps NIL)
     (while (or (> Gap 1) Swaps)
        (setq Gap (max 1 (/ (* Gap 4) 5)))
        (off Swaps)
        (use Lst
           (for (G (cdr (nth Lst Gap))  G  (cdr G))
              (when (> (car Lst) (car G))
                 (xchg Lst G)
                 (on Swaps) )
              (pop 'Lst) ) ) ) )
  Lst )</lang>

Output:

: (combSort (88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70))
-> (0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88)

PL/I

<lang PL/I> /* From the pseudocode. */ comb_sort: procedure (A);

  declare A(*) fixed;
  declare t fixed;
  declare (i, gap) fixed binary (31);
  declare swaps bit (1) aligned;

  gap = hbound(A,1) - lbound(A,1);  /* initialize the gap size. */
  do until (gap <= 1 & swaps);
     /* update the gap value for a next comb. */
     put skip data (gap);
     gap = gap / 1.25e0;
     put skip data (gap);
     swaps = '1'b;
     /* a single "comb" over the array. */
     do i = lbound(A,1) by 1 until (i + gap >= hbound(A,1));
        if A(i) > A(i+gap) then
           do;
              t = A(i); A(i) = A(i+gap); A(i+gap) = t;
              swaps = '0'b; /* Flag a swap has occurred, so */
                            /* the list is not guaranteed sorted. */
           end;
      end;
  end;

end comb_sort; </lang>

PowerShell

Massaging gap to always hit 11. Based on PowerShell from Cocktail Sort <lang PowerShell>function CombSort ($a) {

   $l = $a.Length

$gap = 11 while( $gap -lt $l ) { $gap = [Math]::Floor( $gap*1.3 ) } if( $l -gt 1 ) { $hasChanged = $true :outer while ($hasChanged -or ( $gap -gt 1 ) ) { $count = 0 $hasChanged = $false if( $gap -gt 1 ) { $gap = [Math]::Floor( $gap/1.3 ) } else { $l-- } for ($i = 0; $i -lt ( $l - $gap ); $i++) { if ($a[$i] -gt $a[$i+$gap]) { $a[$i], $a[$i+$gap] = $a[$i+$gap], $a[$i] $hasChanged = $true $count++ } } } } $a }

$l = 100; CombSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( -( $l - 1 ), $l - 1 ) } )</lang>

PureBasic

Implementation of CombSort11. <lang PureBasic>;sorts an array of integers Procedure combSort11(Array a(1))

 Protected i, gap, swaps = 1
 Protected nElements = ArraySize(a())

 gap = nElements
 While (gap > 1) Or (swapped = 1)
   gap * 10 / 13
   If gap = 9 Or gap = 10: gap = 11:  EndIf 
   If gap < 1: gap = 1: EndIf 
     
   i = 0
   swaps = 0 
   While (i + gap) <= nElements
     If a(i) > a(i + gap)
       Swap a(i), a(i + gap)
       swaps = 1
     EndIf
     i + 1
   Wend 
 Wend

EndProcedure</lang> Implementation of CombSort. <lang PureBasic>;sorts an array of integers Procedure combSort(Array a(1))

 Protected i, gap, swaps = 1
 Protected nElements = ArraySize(a())
 
 gap = nElements
 While (gap > 1) Or (swaps = 1)
   gap = Int(gap / 1.25)
   
   i = 0
   swaps = 0 
   While (i + gap) <= nElements
     If a(i) > a(i + gap)
       Swap a(i), a(i + gap)
       swaps = 1
     EndIf
     i + 1
   Wend 
 Wend

EndProcedure</lang>

Python

<lang python>>>> def combsort(input):

   gap = len(input)
   swaps = True
   while gap > 1 or swaps:
       gap = max(1, int(gap / 1.25))  # minimum gap is 1
       swaps = False
       for i in range(len(input) - gap):
           j = i+gap
           if input[i] > input[j]:
               input[i], input[j] = input[j], input[i]
               swaps = True

>>> y = [88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70] >>> combsort(y) >>> assert y == sorted(y) >>> y [0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88] >>> </lang>

Racket

lang racket

(require (only-in srfi/43 vector-swap!))

(define (comb-sort xs)

 (define (ref i) (vector-ref xs i))
 (define (swap i j) (vector-swap! xs i j))
 (define (new gap) (max 1 (exact-floor (/ gap 1.25))))
 (define size (vector-length xs))  
 (let loop ([gap size] [swaps 0])
   (unless (and (= gap 1) (= swaps 0))
     (loop (new gap)
           (for/fold ([swaps 0]) ([i (in-range 0 (- size gap))])
             (cond
               [(> (ref i) (ref (+ i gap)))
                (swap i (+ i gap))
                (+ swaps 1)]
               [swaps])))))
 xs)

</lang>

REXX

Programming note: the REXX statement (line 12) s=trunc(s*.8) could've been expressed as: s=s*.8%1 (which is faster), but is more cryptic. <lang rexx>/*REXX program sorts a stemmed array using the comb sort algorithm. */ call gen; w=length(#) /*generate the @ array elements. */ call show 'before sort' /*display the before array elements. */ say copies('▒',60) /*display a separator line (a fence). */ call combSort # /*invoke the comb sort. */ call show ' after sort' /*display the after array elements. */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────COMBSORT subroutine───────────────────────*/ combSort: procedure expose @.; parse arg N /*N: is number of @ elements. */ s=N-1 /*S: is the spread between COMBs.*/

      do  until  s<=1 & done;  done=1       /*assume sort is done  (so far). */
      s=trunc(s*.8)                         /*   ÷   is slow,   *  is better.*/
         do j=1  until js>=N;    js=j+s
         if @.j>@.js  then  do;  _=@.j;  @.j=@.js;  @.js=_;  done=0;  end
         end   /*j*/
      end      /*until*/

return /*──────────────────────────────────GEN subroutine────────────────────────────*/ gen: @. = ; @.12 = 'dodecagon 12'

           @.1  = '----polygon---  sides'    ;    @.13 = 'tridecagon        13'
           @.2  = '============== ======='   ;    @.14 = 'tetradecagon      14'
           @.3  = 'triangle           3'     ;    @.15 = 'pentadecagon      15'
           @.4  = 'quadrilateral      4'     ;    @.16 = 'hexadecagon       16'
           @.5  = 'pentagon           5'     ;    @.17 = 'heptadecagon      17'
           @.6  = 'hexagon            6'     ;    @.18 = 'octadecagon       18'
           @.7  = 'heptagon           7'     ;    @.19 = 'enneadecagon      19'
           @.8  = 'octagon            8'     ;    @.20 = 'icosagon          20'
           @.9  = 'nonagon            9'     ;    @.21 = 'hectogon         100'
           @.10 = 'decagon           10'     ;    @.22 = 'chiliagon       1000'
           @.11 = 'hendecagon        11'     ;    @.23 = 'myriagon       10000'
 do #=1  while @.#\==; end;   #=#-1 /*determine how many entries in @ array*/

return /*──────────────────────────────────SHOW subroutine───────────────────────────*/ show: do j=1 for #; say ' element' right(j,w) arg(1)":" @.j; end; return</lang> Data note: A hendecagon (also known as an undecagon or unidecagon) it is from the Greek word hendeka [eleven] and gon─ [corner].

output

        element  1 before sort: ----polygon---  sides
        element  2 before sort: ============== =======
        element  3 before sort: triangle           3
        element  4 before sort: quadrilateral      4
        element  5 before sort: pentagon           5
        element  6 before sort: hexagon            6
        element  7 before sort: heptagon           7
        element  8 before sort: octagon            8
        element  9 before sort: nonagon            9
        element 10 before sort: decagon           10
        element 11 before sort: hendecagon        11
        element 12 before sort: dodecagon         12
        element 13 before sort: tridecagon        13
        element 14 before sort: tetradecagon      14
        element 15 before sort: pentadecagon      15
        element 16 before sort: hexadecagon       16
        element 17 before sort: heptadecagon      17
        element 18 before sort: octadecagon       18
        element 19 before sort: enneadecagon      19
        element 20 before sort: icosagon          20
        element 21 before sort: hectogon         100
        element 22 before sort: chiliagon       1000
        element 23 before sort: myriagon       10000
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
        element  1  after sort: ----polygon---  sides
        element  2  after sort: ============== =======
        element  3  after sort: chiliagon       1000
        element  4  after sort: decagon           10
        element  5  after sort: dodecagon         12
        element  6  after sort: enneadecagon      19
        element  7  after sort: hectogon         100
        element  8  after sort: hendecagon        11
        element  9  after sort: heptadecagon      17
        element 10  after sort: heptagon           7
        element 11  after sort: hexadecagon       16
        element 12  after sort: hexagon            6
        element 13  after sort: icosagon          20
        element 14  after sort: myriagon       10000
        element 15  after sort: nonagon            9
        element 16  after sort: octadecagon       18
        element 17  after sort: octagon            8
        element 18  after sort: pentadecagon      15
        element 19  after sort: pentagon           5
        element 20  after sort: quadrilateral      4
        element 21  after sort: tetradecagon      14
        element 22  after sort: triangle           3
        element 23  after sort: tridecagon        13

Ruby

<lang ruby>class Array

 def combsort!
   gap = size
   swaps = true
   while gap > 1 or swaps
     gap = [1, (gap / 1.25).to_i].max
     swaps = false
     0.upto(size - gap - 1) do |i|
       if self[i] > self[i+gap]
         self[i], self[i+gap] = self[i+gap], self[i]
         swaps = true
       end
     end
   end
   self
 end

end

p [23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78].combsort!</lang> results in

[12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

Sather

<lang sather>class SORT{T < $IS_LT{T}} is

 private swap(inout a, inout b:T) is
   temp ::= a;
   a := b;
   b := temp;
 end;

-- ---------------------------------------------------------------------------------

 comb_sort(inout a:ARRAY{T}) is
   gap ::= a.size;
   swapped ::= true;
   loop until!(gap <= 1 and ~swapped);
     if gap > 1 then
       gap := (gap.flt / 1.25).int;
     end;
     i ::= 0;
     swapped := false;
     loop until! ( (i + gap) >= a.size );
       if (a[i] > a[i+gap]) then

swap(inout a[i], inout a[i+gap]); swapped := true; end;

       i := i + 1;
     end;
   end;
 end;

end;

class MAIN is

 main is
   a:ARRAY{INT} := |88, 18, 31, 44, 4, 0, 8, 81, 14, 78, 20, 76, 84, 33, 73, 75, 82, 5, 62, 70|;
   b ::= a.copy;
   SORT{INT}::comb_sort(inout b);
   #OUT + b + "\n";
 end;

end;</lang>

Sidef

<lang ruby>func comb_sort(arr) {

   var gap = arr.len;
   var swaps = true;
   while (gap > 1 || swaps) {
       gap.div!(1.25).int! if (gap > 1);
       swaps = false;
       (arr.len - gap).range.each { |i|
           if (arr[i] > arr[i+gap]) {
               arr[i, i+gap] = arr[i+gap, i];
               swaps = true;
           }
       }
   }
   return arr;

}</lang>

Swift

Translation of: C

<lang Swift>func combSort(inout list:[Int]) {

   var swapped = true
   var gap = list.count
   
   while gap > 1 || swapped {
       gap = gap * 10 / 13
       
       if gap == 9 || gap == 10 {
           gap = 11
       } else if gap < 1 {
           gap = 1
       }
       
       swapped = false
       
       for var i = 0, j = gap; j < list.count; i++, j++ {
           if list[i] > list[j] {
               (list[i], list[j]) = (list[j], list[i])
               swapped = true
           }
       }
   }

}</lang>

Tcl

<lang tcl>proc combsort {input} {

   set gap [llength $input]
   while 1 {

set gap [expr {int(floor($gap / 1.3))}] set swaps 0 for {set i 0} {$i+$gap < [llength $input]} {incr i} { set j [expr {$i+$gap}] if {[lindex $input $i] > [lindex $input $j]} { set tmp [lindex $input $i] lset input $i [lindex $input $j] lset input $j $tmp incr swaps } } if {$gap <= 1 && !$swaps} break

   }
   return $input

}

set data {23 76 99 58 97 57 35 89 51 38 95 92 24 46 31 24 14 12 57 78} puts [combsort $data]</lang> Produces this output:

12 14 23 24 24 31 35 38 46 51 57 57 58 76 78 89 92 95 97 99

TI-83 BASIC

Requires prgmSORTINS. Gap division of 1.3. Switches to Insertion sort when gap is less than 5.

:L₁→L₂
:dim(L₂)→A
:While A>5 and B=0
:int(A/1.3)→A
:1→C
:0→B
:While (C+A)≥dim(L₂)
:If L₂(C)>L₂(C+A)
:Then
:L₂(C)→D
:L₂(C+A)→L₂(C)
:D→L₂(C+A)
:1→B
:End
:C+1→C
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:L₁→L₃
:L₂→L₁
:prgmSORTINS
:L₃→L₁
:DelVar L₃
:Return

uBasic/4tH

<lang>PRINT "Comb sort:"

 n = FUNC (_InitArray)
 PROC _ShowArray (n)
 PROC _Combsort (n)
 PROC _ShowArray (n)

PRINT

END

_Combsort PARAM (1) ' Combsort subroutine

 LOCAL(4)
 b@ = a@
 c@ = 1

 DO WHILE (b@ > 1) + c@

   b@ = (b@ * 10) / 13

   IF (b@ = 9) + (b@ = 10) THEN b@ = 11
   IF b@ < 1 THEN b@ = 1

   c@ = 0
   d@ = 0
   e@ = b@

   DO WHILE e@ < a@
     IF @(d@) > @(e@) THEN PROC _Swap (d@, e@) : c@ = 1
     d@ = d@ + 1
     e@ = e@ + 1
   LOOP
 LOOP

RETURN

_Swap PARAM(2) ' Swap two array elements

 PUSH @(a@)
 @(a@) = @(b@)
 @(b@) = POP()

RETURN

_InitArray ' Init example array

 PUSH 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

 FOR i = 0 TO 9
   @(i) = POP()
 NEXT

RETURN (i)

_ShowArray PARAM (1) ' Show array subroutine

 FOR i = 0 TO a@-1
   PRINT @(i),
 NEXT

 PRINT

RETURN</lang>