Sorting algorithms/Comb sort

From Rosetta Code
(Redirected from Comb sort)
This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.
Task
Sorting algorithms/Comb sort
You are encouraged to solve this task according to the task description, using any language you may know.
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     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


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



11l

Translation of: Python
F combsort(&input)
   V gap = input.len
   V swaps = 1B
   L gap > 1 | swaps
      gap = max(1, Int(gap / 1.25))
      swaps = 0B
      L(i) 0 .< input.len - gap
         V j = i + gap
         I input[i] > input[j]
            swap(&input[i], &input[j])
            swaps = 1B

V 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))
print(y)
Output:
[0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]

360 Assembly

Translation from prototype.
The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible.

*        Comb sort                 23/06/2016
COMBSORT CSECT
         USING  COMBSORT,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    prolog
         ST     R13,4(R15)         "
         ST     R15,8(R13)         " 
         LR     R13,R15            "
         L      R2,N               n
         BCTR   R2,0               n-1
         ST     R2,GAP             gap=n-1
         DO     UNTIL=(CLC,GAP,EQ,=F'1',AND,CLI,SWAPS,EQ,X'00') repeat
         L      R4,GAP               gap                             |
         MH     R4,=H'100'           gap*100                         |
         SRDA   R4,32                .                               |
         D      R4,=F'125'           /125                            |
         ST     R5,GAP               gap=int(gap/1.25)               |
         IF     CLC,GAP,LT,=F'1'     if gap<1 then  -----------+     |
         MVC    GAP,=F'1'              gap=1                   |     |
         ENDIF  ,                    end if  <-----------------+     |
         MVI    SWAPS,X'00'          swaps=false                     |
         LA     RI,1                 i=1                             |
         DO     UNTIL=(C,R3,GT,N)    do i=1 by 1 until i+gap>n  ---+ |
         LR     R7,RI                  i                           | |
         SLA    R7,2                   .                           | |
         LA     R7,A-4(R7)             r7=@a(i)                    | |
         LR     R8,RI                  i                           | |
         A      R8,GAP                 i+gap                       | |
         SLA    R8,2                   .                           | |
         LA     R8,A-4(R8)             r8=@a(i+gap)                | |
         L      R2,0(R7)               temp=a(i)                   | |
         IF     C,R2,GT,0(R8)          if a(i)>a(i+gap) then  ---+ | |
         MVC    0(4,R7),0(R8)            a(i)=a(i+gap)           | | |
         ST     R2,0(R8)                 a(i+gap)=temp           | | |
         MVI    SWAPS,X'01'              swaps=true              | | |
         ENDIF  ,                      end if  <-----------------+ | |
         LA     RI,1(RI)               i=i+1                       | |
         LR     R3,RI                  i                           | |
         A      R3,GAP                 i+gap                       | |
         ENDDO  ,                    end do  <---------------------+ |
         ENDDO  ,                  until gap=1 and not swaps  <------+
         LA     R3,PG              pgi=0
         LA     RI,1               i=1
         DO     WHILE=(C,RI,LE,N)  do i=1 to n  -------+
         LR     R1,RI                i                 |
         SLA    R1,2                 .                 |
         L      R2,A-4(R1)           a(i)              |
         XDECO  R2,XDEC              edit a(i)         |
         MVC    0(4,R3),XDEC+8       output a(i)       |
         LA     R3,4(R3)             pgi=pgi+4         |
         LA     RI,1(RI)             i=i+1             |
         ENDDO  ,                  end do  <-----------+
         XPRNT  PG,L'PG            print buffer
         L      R13,4(0,R13)       epilog 
         LM     R14,R12,12(R13)    "
         XR     R15,R15            "
         BR     R14                exit
A     DC F'4',F'65',F'2',F'-31',F'0',F'99',F'2',F'83',F'782',F'1'
      DC F'45',F'82',F'69',F'82',F'104',F'58',F'88',F'112',F'89',F'74'
N        DC     A((N-A)/L'A)       number of items of a
GAP      DS     F                  gap
SWAPS    DS     X                  flag for swaps
PG       DS     CL80               output buffer
XDEC     DS     CL12               temp for edit
         YREGS
RI       EQU    6                  i
         END    COMBSORT
Output:
 -31   0   1   2   2   4  45  58  65  69  74  82  82  83  88  89  99 104 112 782

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
/* ARM assembly AARCH64 Raspberry PI 3B */
/*  program combSort64.s  */
 
/*******************************************/
/* Constantes file                         */
/*******************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeConstantesARM64.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .quad   1,3,6,2,5,9,10,8,4,7
TableNumber:     .quad   10,9,8,7,6,-5,4,3,2,1
                 .equ NBELEMENTS, (. - TableNumber) / 8 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:       .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              // entry of program 
    ldr x0,qAdrTableNumber                         // address number table
    mov x1,0
    mov x2,NBELEMENTS                              // number of élements 
    bl combSort
    ldr x0,qAdrTableNumber                         // address number table
    bl displayTable
 
    ldr x0,qAdrTableNumber                         // address number table
    mov x1,NBELEMENTS                              // number of élements 
    bl isSorted                                    // control sort
    cmp x0,1                                       // sorted ?
    beq 1f                                    
    ldr x0,qAdrszMessSortNok                       // no !! error sort
    bl affichageMess
    b 100f
1:                                                 // yes
    ldr x0,qAdrszMessSortOk
    bl affichageMess
100:                                               // standard end of the program 
    mov x0,0                                       // return code
    mov x8,EXIT                                    // request to exit program
    svc 0                                          // perform the system call
 
qAdrsZoneConv:            .quad sZoneConv
qAdrszCarriageReturn:     .quad szCarriageReturn
qAdrsMessResult:          .quad sMessResult
qAdrTableNumber:          .quad TableNumber
qAdrszMessSortOk:         .quad szMessSortOk
qAdrszMessSortNok:        .quad szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the number of elements  > 0  */
/* x0 return 0  if not sorted   1  if sorted */
isSorted:
    stp x2,lr,[sp,-16]!              // save  registers
    stp x3,x4,[sp,-16]!              // save  registers
    mov x2,0
    ldr x4,[x0,x2,lsl 3]
1:
    add x2,x2,1
    cmp x2,x1
    bge 99f
    ldr x3,[x0,x2, lsl 3]
    cmp x3,x4
    blt 98f
    mov x4,x3
    b 1b
98:
    mov x0,0                       // not sorted
    b 100f
99:
    mov x0,1                       // sorted
100:
    ldp x3,x4,[sp],16              // restaur  2 registers
    ldp x2,lr,[sp],16              // restaur  2 registers
    ret                            // return to address lr x30
/******************************************************************/
/*         comb sort                                              */ 
/******************************************************************/
/* x0 contains the address of table */
/* x1 contains the first element    */
/* x2 contains the number of element */
/* this routine use à factor to 1.28  see wikipedia for best factor */
combSort:
    stp x1,lr,[sp,-16]!        // save  registers
    stp x2,x3,[sp,-16]!        // save  registers
    stp x4,x5,[sp,-16]!        // save  registers
    stp x6,x7,[sp,-16]!        // save  registers
    stp x8,x9,[sp,-16]!        // save  registers
    sub x9,x2,x1               // compute gap
    sub x2,x2,1                // compute end index n - 1
    mov x7,100
1:                             // start loop 1
    mul x9,x7,x9               // gap multiply by 100
    lsr x9,x9,7                // divide by 128
    cmp x9,0
    mov x3,1
    csel x9,x9,x3,ne
    mov x3,x1                  // start index
    mov x8,0                   // swaps
2:                             // start loop 2
    add x4,x3,x9               // add gap to indice
    cmp x4,x2
    bgt 4f
    ldr x5,[x0,x3,lsl 3]       // load value A[j]
    ldr x6,[x0,x4,lsl 3]       // load value A[j+1]
    cmp x6,x5                  // compare value
    bge 3f 
    str x6,[x0,x3,lsl 3]       // if smaller inversion
    str x5,[x0,x4,lsl 3] 
    mov x8,1                   // swaps
3:
    add x3,x3,1                // increment index j
    b 2b

4:
    //bl displayTable
    cmp x9,1                   // gap = 1 ?
    bne 1b                     // no loop
    cmp x8,1                   // swaps ?
    beq 1b                     // yes -> loop 1
 
100:
    ldp x8,x9,[sp],16          // restaur  2 registers
    ldp x6,x7,[sp],16          // restaur  2 registers
    ldp x4,x5,[sp],16          // restaur  2 registers
    ldp x2,x3,[sp],16          // restaur  2 registers
    ldp x1,lr,[sp],16          // restaur  2 registers
    ret                        // return to address lr x30
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* x0 contains the address of table */
displayTable:
    stp x1,lr,[sp,-16]!              // save  registers
    stp x2,x3,[sp,-16]!              // save  registers
    mov x2,x0                        // table address
    mov x3,0
1:                                   // loop display table
    ldr x0,[x2,x3,lsl 3]
    ldr x1,qAdrsZoneConv
    bl conversion10S                  // décimal conversion
    ldr x0,qAdrsMessResult
    ldr x1,qAdrsZoneConv
    bl strInsertAtCharInc            // insert result at @ character
    bl affichageMess                 // display message
    add x3,x3,1
    cmp x3,NBELEMENTS - 1
    ble 1b
    ldr x0,qAdrszCarriageReturn
    bl affichageMess
    mov x0,x2
100:
    ldp x2,x3,[sp],16               // restaur  2 registers
    ldp x1,lr,[sp],16               // restaur  2 registers
    ret                             // return to address lr x30
/********************************************************/
/*        File Include fonctions                        */
/********************************************************/
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"

Action!

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

PROC CombSort(INT ARRAY a INT size)
  INT gap,i,tmp
  BYTE swaps

  gap=size swaps=0
  WHILE gap#1 OR swaps#0
  DO
    gap=(gap*5)/4
    IF gap<1 THEN gap=1 FI

    i=0
    swaps=0

    WHILE i+gap<size
    DO
      IF a(i)>a(i+1) THEN
        tmp=a(i) a(i)=a(i+1) a(i+1)=tmp
        swaps=1
      FI
      i==+1
    OD
  OD
RETURN

PROC Test(INT ARRAY a INT size)
  PrintE("Array before sort:")
  PrintArray(a,size)
  CombSort(a,size)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN

PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 3 7 4 8 20 65530],
    b(21)=[10 9 8 7 6 5 4 3 2 1 0
      65535 65534 65533 65532 65531
      65530 65529 65528 65527 65526],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
  
  Test(a,10)
  Test(b,21)
  Test(c,8)
  Test(d,12)
RETURN
Output:

Screenshot from Atari 8-bit computer

Array before sort:
[1 4 -1 0 3 7 4 8 20 -6]
Array after sort:
[-6 -1 0 1 3 4 4 7 8 20]

Array before sort:
[10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10]
Array after sort:
[-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10]

Array before sort:
[101 102 103 104 105 106 107 108]
Array after sort:
[101 102 103 104 105 106 107 108]

Array before sort:
[1 -1 1 -1 1 -1 1 -1 1 -1 1 -1]
Array after sort:
[-1 -1 -1 -1 -1 -1 1 1 1 1 1 1]

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;
}

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;

Output:

-1 0 1 3 3 4 256

ALGOL 68

Library: ALGOL 68-rows
BEGIN # comb sort #
    PR read "rows.incl.a68" PR # include row (array) utilities - SHOW is used to display the array #
    # comb-sorts in-place the array of integers input #
    PROC comb sort = ( REF[]INT input )VOID:
         IF INT  input size = ( UPB input - LWB input ) + 1;
            input size > 1
         THEN # more than one element, so must sort #
            INT  gap     := input size; # initial gap is the whole array size #
            BOOL swapped := TRUE;
            WHILE gap /= 1 OR swapped DO
                # update the gap value for a next comb #
                gap := ENTIER ( gap / 1.25 );
                IF gap < 1 THEN
                    # ensure the gap is at least 1 #
                    gap := 1
                FI;
                INT i := LWB input;
                swapped := FALSE;
                # a single "comb" over the input list #
                FOR i FROM LWB input WHILE i + gap <= UPB input DO
                    INT t     = input[ i ];
                    INT i gap = i + gap;
                    IF t > input[ i gap ] THEN
                        # need to swap out-of-order items #
                        input[ i     ] := input[ i gap ];
                        input[ i gap ] := t;
                        swapped := TRUE # Flag a swap has occurred, so the list is not guaranteed sorted yet #
                    FI
                OD
            OD
         FI # comb sort # ;
    # test #
    [ 1 : 7 ]INT data := ( 9, -4, 0, 2, 3, 77, 1 );  # data to sort #
    SHOW data;
    comb sort( data );
    print( ( " -> " ) );
    SHOW data
END
Output:
 9 -4 0 2 3 77 1 ->  -4 0 1 2 3 9 77

ALGOL W

Translation of: ALGOL 68
begin % comb sort %
    % comb-sorts in-place the array of integers input with bounds lb :: ub %
    procedure combSort ( integer array input ( * )
                       ; integer value lb, ub
                       ) ;
    begin
        integer inputSize, gap, i;
        inputSize := ( ub - lb ) + 1;
        if inputSize > 1 then begin
            % more than one element, so must sort %
            logical swapped;
            gap     := inputSize; % initial gap is the whole array size %
            swapped := true;
            while gap not = 1 or swapped do begin
                % update the gap value for a next comb %
                gap := entier( gap / 1.25 );
                if gap < 1 then begin
                    % ensure the gap is at least 1 %
                    gap := 1
                end if_gap_lt_1 ;
                swapped := false;
                % a single "comb" over the input list %
                i := lb;
                while i + gap <= ub do begin
                    integer t, iGap;
                    t    := input( i );
                    iGap := i + gap;
                    if t > input( iGap ) then begin
                        % need to swap out-of-order items %
                        input( i    ) := input( iGap );
                        input( iGap ) := t;
                        swapped := true % Flag a swap has occurred, so the list is not guaranteed sorted yet %
                    end if_t_gt_input__iGap ;
                    i := i + 1
                end while_i_plus_gap_le_ub
            end while_gap_ne_1_or_swapped
        end if_inputSize_gt_1
    end combSort ;
    begin % test %
        integer array data ( 1 :: 7 );
        integer       dPos;
        dPos := 0;
        for v := 9, -4, 0, 2, 3, 77, 1 do begin dPos := dPos + 1; data( dPos ) := v end;
        for i := 1 until 7 do writeon( i_w := 1, s_w := 0, " ", data( i ) );
        combSort( data, 1, 7 );
        writeon( ( " -> " ) );
        for i := 1 until 7 do writeon( i_w := 1, s_w := 0, " ", data( i ) )
    end
end.
Output:
 9 -4 0 2 3 77 1 ->  -4 0 1 2 3 9 77

AppleScript

-- Comb sort with insertion sort finish.
-- Comb sort algorithm: Włodzimierz Dobosiewicz and Artur Borowy, 1980. Stephen Lacey and Richard Box, 1991.

on combSort(theList, l, r) -- Sort items l thru r of theLIst.
    set listLen to (count theList)
    if (listLen < 2) then return
    -- Negative and/or transposed range indices.
    if (l < 0) then set l to listLen + l + 1
    if (r < 0) then set r to listLen + r + 1
    if (l > r) then set {l, r} to {r, l}
    
    script o
        property lst : theList
    end script
    
    -- This implementation performs fastest with a comb gap divisor of 1.4
    -- and the insertion sort taking over when the gap's down to 8 or less.
    set divisor to 1.4
    set gap to (r - l + 1) div divisor
    repeat while (gap > 8)
        repeat with i from l to (r - gap)
            set j to i + gap
            set lv to o's lst's item i
            set rv to o's lst's item j
            if (lv > rv) then
                set o's lst's item i to rv
                set o's lst's item j to lv
            end if
        end repeat
        set gap to gap div divisor
    end repeat
    
    insertionSort(theList, l, r)
    
    return -- nothing.
end combSort

on insertionSort(theList, l, r) -- Sort items l thru r of theList.
    set listLength to (count theList)
    if (listLength < 2) then return
    if (l < 0) then set l to listLength + l + 1
    if (r < 0) then set r to listLength + r + 1
    if (l > r) then set {l, r} to {r, l}
    
    script o
        property lst : theList
    end script
    
    set highestSoFar to o's lst's item l
    set rv to o's lst's item (l + 1)
    if (highestSoFar > rv) then
        set o's lst's item l to rv
    else
        set highestSoFar to rv
    end if
    repeat with j from (l + 2) to r
        set rv to o's lst's item j
        if (highestSoFar > rv) then
            repeat with i from (j - 2) to l by -1
                set lv to o's lst's item i
                if (lv > rv) then
                    set o's lst's item (i + 1) to lv
                else
                    set i to i + 1
                    exit repeat
                end if
            end repeat
            set o's lst's item i to rv
        else
            set o's lst's item (j - 1) to highestSoFar
            set highestSoFar to rv
        end if
    end repeat
    set o's lst's item r to highestSoFar
    
    return -- nothing.
end insertionSort

-- Demo:
local aList
set aList to {7, 56, 70, 22, 94, 42, 5, 25, 54, 90, 29, 65, 87, 27, 4, 5, 86, 8, 2, 30, 87, 12, 85, 86, 7}
combSort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
aList
Output:
{2, 4, 5, 5, 7, 7, 8, 12, 22, 25, 27, 29, 30, 42, 54, 56, 65, 70, 85, 86, 86, 87, 87, 90, 94}

ARM Assembly

Works with: as version Raspberry Pi
/* ARM assembly Raspberry PI  */
/*  program combSort.s  */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"

/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessSortOk:       .asciz "Table sorted.\n"
szMessSortNok:      .asciz "Table not sorted !!!!!.\n"
sMessResult:        .asciz "Value  : @ \n"
szCarriageReturn:   .asciz "\n"
 
.align 4
#TableNumber:      .int   1,3,6,2,5,9,10,8,4,7
TableNumber:       .int   10,9,8,7,6,5,4,3,2,1
                   .equ NBELEMENTS, (. - TableNumber) / 4
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:            .skip 24
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                              @ entry of program 
 
1:
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#0
    mov r2,#NBELEMENTS                             @ number of élements 
    bl combSort
    ldr r0,iAdrTableNumber                         @ address number table
    bl displayTable
 
    ldr r0,iAdrTableNumber                         @ address number table
    mov r1,#NBELEMENTS                             @ number of élements 
    bl isSorted                                    @ control sort
    cmp r0,#1                                      @ sorted ?
    beq 2f                                    
    ldr r0,iAdrszMessSortNok                       @ no !! error sort
    bl affichageMess
    b 100f
2:                                                 @ yes
    ldr r0,iAdrszMessSortOk
    bl affichageMess
100:                                               @ standard end of the program 
    mov r0, #0                                     @ return code
    mov r7, #EXIT                                  @ request to exit program
    svc #0                                         @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrTableNumber:          .int TableNumber
iAdrszMessSortOk:         .int szMessSortOk
iAdrszMessSortNok:        .int szMessSortNok
/******************************************************************/
/*     control sorted table                                   */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the number of elements  > 0  */
/* r0 return 0  if not sorted   1  if sorted */
isSorted:
    push {r2-r4,lr}                                    @ save registers
    mov r2,#0
    ldr r4,[r0,r2,lsl #2]
1:
    add r2,#1
    cmp r2,r1
    movge r0,#1
    bge 100f
    ldr r3,[r0,r2, lsl #2]
    cmp r3,r4
    movlt r0,#0
    blt 100f
    mov r4,r3
    b 1b
100:
    pop {r2-r4,lr}
    bx lr                                              @ return 
/******************************************************************/
/*         comb Sort                                          */ 
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first element    */
/* r2 contains the number of element */
/* this routine use à factor to 1.28  see wikipedia for best factor */
combSort:
    push {r1-r9,lr}           @ save registers
    sub r9,r2,r1              @ compute gap
    sub r2,r2,#1              @ compute end index = n - 1
    mov r7,#100
1:                            @ start loop 1
    mul r9,r7,r9              @ gap multiply by 100
    lsrs r9,#7                @ divide by 128   equi * 0,78125 equi divide by 1,28
    moveq r9,#1               @ if gap = 0 -> gap = 1
    mov r8,#0                 @ swaps
    mov r3,r1                 @ indice
2:                            @ start loop 2
    add r4,r3,r9
    cmp r4,r2                 @ end ?
    bgt 3f
    ldr r5,[r0,r3,lsl #2]     @ load value A[j]
    ldr r6,[r0,r4,lsl #2]     @ load value A[j+1]
    cmp r6,r5                 @ compare value
    strlt r6,[r0,r3,lsl #2]   @ if smaller inversion
    strlt r5,[r0,r4,lsl #2] 
    movlt r8,#1               @ swaps = 1
    add r3,#1                 @ increment indice
    b 2b                      @ loop 2
     
3:
    @ bl displayTable
    cmp r9,#1                 @ gap = 1 ?
    bne 1b
    cmp r8,#1                 @ swaps ?
    beq 1b                    @ yes -> loop 1
 
100:
    pop {r1-r9,lr}
    bx lr                                                  @ return 
 
/******************************************************************/
/*      Display table elements                                */ 
/******************************************************************/
/* r0 contains the address of table */
displayTable:
    push {r0-r3,lr}                                    @ save registers
    mov r2,r0                                          @ table address
    mov r3,#0
1:                                                     @ loop display table
    ldr r0,[r2,r3,lsl #2]
    ldr r1,iAdrsZoneConv                               @ 
    bl conversion10S                                    @ décimal conversion 
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv                               @ insert conversion
    bl strInsertAtCharInc
    bl affichageMess                                   @ display message
    add r3,#1
    cmp r3,#NBELEMENTS - 1
    ble 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
100:
    pop {r0-r3,lr}
    bx lr
iAdrsZoneConv:           .int sZoneConv
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"

Arturo

combSort: function [items][
    a: new items
    gap: size a
    swapped: true

    while [or? gap > 1 swapped][
        gap: (gap * 10) / 13
        if or? gap=9 gap=10 -> gap: 11
        if gap<1 -> gap: 1
        swapped: false
        i: 0
        loop gap..dec size items 'j [
            if a\[i] > a\[j] [
                tmp: a\[i]
                a\[i]: a\[j]
                a\[j]: tmp
                swapped: true
            ]
            i: i + 1
        ]
    ]
    return a
]

print combSort [3 1 2 8 5 7 9 4 6]
Output:
1 2 3 4 5 6 7 8 9

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
}

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

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]
}

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

C

Implementation of Combsort11. Its efficiency can be improved by just switching to Insertion sort when the gap size becomes less than 10.

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;
      }
    }
  }
}

C#

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;
        }
    }
}

C++

This is copied from the Wikipedia article.

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;
            }
        }
    }
}

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.

       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.

Common Lisp

(defparameter *shrink* 1.3)

(defun comb-sort (input)
  (loop with input-size = (length input)
        with gap = input-size
        with swapped
        do (when (> gap 1)
             (setf gap (floor gap *shrink*)))
           (setf swapped nil)
           (loop for lo from 0
                 for hi from gap below input-size
                 when (> (aref input lo) (aref input hi))
                   do (rotatef (aref input lo) (aref input hi))
                      (setf swapped t))
        while (or (> gap 1) swapped)
        finally (return input)))

D

Translation of: Python
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;
}
Output:
[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

Delphi

Adaptation of Pascal

program Comb_sort;

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Types;

type
  THelperIntegerDynArray = record helper for TIntegerDynArray
  public
    procedure CombSort;
    procedure FillRange(Count: integer);
    procedure Shuffle;
    function ToString: string;
  end;

{ THelperIntegerDynArray }
procedure THelperIntegerDynArray.CombSort;
var
  i, gap, temp: integer;
  swapped: boolean;
begin
  gap := length(self);
  swapped := true;
  while (gap > 1) or swapped do
  begin
    gap := trunc(gap / 1.3);
    if (gap < 1) then
      gap := 1;
    swapped := false;
    for i := 0 to length(self) - gap - 1 do
      if self[i] > self[i + gap] then
      begin
        temp := self[i];
        self[i] := self[i + gap];
        self[i + gap] := temp;
        swapped := true;
      end;
  end;
end;

procedure THelperIntegerDynArray.FillRange(Count: integer);
var
  i: Integer;
begin
  SetLength(self, Count);
  for i := 0 to Count - 1 do
    Self[i] := i;
end;

procedure THelperIntegerDynArray.Shuffle;
var
  i, j, tmp: integer;
  count: integer;
begin
  Randomize;
  count := Length(self);
  for i := 0 to count - 1 do
  begin
    j := i + Random(count - i);
    tmp := self[i];
    self[i] := self[j];
    self[j] := tmp;
  end;
end;

function THelperIntegerDynArray.ToString: string;
var
  value: Integer;
begin
  Result := '';
  for value in self do
  begin
    Result := Result + ' ' + Format('%4d', [value]);
  end;
  Result := '[' + Result.Trim + ']';
end;

var
  data: TIntegerDynArray;

begin
  data.FillRange(10);
  data.Shuffle;
  writeln('The data before sorting:');
  Writeln(data.ToString, #10);

  data.CombSort;

  writeln('The data after sorting:');
  Writeln(data.ToString, #10);

  Readln;
end.
Output:
The data before sorting:
[1    9    0    6    2    7    3    5    4    8]

The data after sorting:
[0    1    2    3    4    5    6    7    8    9]

EasyLang

proc combsort . d[] .
   gap = len d[]
   while gap > 1 or swaps = 1
      gap = higher 1 (gap div 1.25)
      swaps = 0
      for i = 1 to len d[] - gap
         j = i + gap
         if d[i] > d[j]
            swap d[i] d[j]
            swaps = 1
         .
      .
   .
.
d[] = [ 88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70 ]
combsort d[]
print d[]
Output:
[ 0 4 5 8 14 18 20 31 33 44 62 70 73 75 76 78 81 82 84 88 ]

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

Test:

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
Output:
unsorted:
1 5 99 2 95 7 -7
sorted:
-7 1 2 5 7 95 99

Elena

ELENA 5.0 :

import extensions;
import system'math;
import system'routines;
 
extension op
{
    combSort()
    {
        var list := self.clone();
 
        real gap := list.Length;
        bool swaps := true;
        while (gap > 1 || swaps)
        {
            gap /= 1.247330950103979r;
            if (gap<1) { gap := 1 };
 
            int i := 0;
            swaps := false;
            while (i + gap.RoundedInt < list.Length)
            {
                int igap := i + gap.RoundedInt;
                if (list[i] > list[igap])
                {
                    list.exchange(i,igap);
                    swaps := true
                };
                i += 1
            }
        };
 
        ^ list        
    }
}
 
public program()
{
    var list := new int[]{3, 5, 1, 9, 7, 6, 8, 2, 4 };
 
    console.printLine("before:", list.asEnumerable());
    console.printLine("after :", list.combSort().asEnumerable())
}
Output:
before:3,5,1,9,7,6,8,2,4
after :1,2,3,4,5,6,7,8,9

Elixir

defmodule Sort do
  def comb_sort([]), do: []
  def comb_sort(input) do
    comb_sort(List.to_tuple(input), length(input), 0) |> Tuple.to_list
  end
  
  defp comb_sort(output, 1, 0), do: output
  defp comb_sort(input, gap, _) do
    gap = max(trunc(gap / 1.25), 1)
    {output,swaps} = Enum.reduce(0..tuple_size(input)-gap-1, {input,0}, fn i,{acc,swap} ->
      if (x = elem(acc,i)) > (y = elem(acc,i+gap)) do
        {acc |> put_elem(i,y) |> put_elem(i+gap,x), 1}
      else
        {acc,swap}
      end
    end)
    comb_sort(output, gap, swaps)
  end
end

(for _ <- 1..20, do: :rand.uniform(20)) |> IO.inspect |> Sort.comb_sort |> IO.inspect
Output:
[10, 7, 8, 13, 4, 11, 13, 12, 18, 11, 5, 7, 3, 4, 15, 1, 17, 16, 7, 14]
[1, 3, 4, 4, 5, 7, 7, 7, 8, 10, 11, 11, 12, 13, 13, 14, 15, 16, 17, 18]

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.

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

Less Clever Version

This version is an academic demonstration that aligns with the algorithm. As is, it is limited to use one static array and sorts in ascending order only.

\ combsort for the Forth Newbie (GForth)
HEX
\ gratuitous variables for clarity
0 VALUE  GAP
VARIABLE SORTED

DECIMAL
100 CONSTANT SIZE

\ allocate a small array of cells
CREATE Q   SIZE 2+  CELLS ALLOT

\ operator to index into the array
: ]Q  ( n -- adr) CELLS Q + ;

\ fill array and see array
: INITDATA ( -- )      SIZE 0 DO  SIZE I -  I ]Q !  LOOP ;
: SEEDATA  ( -- )  CR  SIZE 0 DO  I ]Q @ U.   LOOP ;

\ divide by 1.35 using Forth's scaling operator
\ found this ratio to be the fastest
: 1.35/  ( n -- n' ) 100 135 */ ;

: XCHG  ( adr1 adr2 -- ) OVER @ OVER @ SWAP ROT !  SWAP ! ;

: COMBSORT ( n -- )
    DUP  TO GAP                      \ set GAP to n
    BEGIN
      GAP 1.35/  TO GAP              \ re-compute the gap
      SORTED ON
      DUP ( -- n) GAP -  0           \ n-gap is loop limit
      DO
         I GAP + ]Q @  I ]Q @ <
         IF
            I GAP + ]Q  I ]Q XCHG    \ Exchange the data in the cells
            SORTED OFF               \ flag we are not sorted
         THEN
      LOOP
      SORTED @  GAP 0=  AND          \ test for complete
   UNTIL
   DROP
;

Fortran

Works with: Fortran version 90 and later
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

FreeBASIC

' 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
Output:
normal comb sort
unsorted   -6   5  -1  -3  -7   6   1   7  -4   3   4  -2  -5   0   2
  sorted   -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7

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

Gambas

Click this link to run this code

Public Sub Main()
Dim siToSort As Short[] = [249, 28, 111, 36, 171, 98, 29, 448, 44, 147, 154, 46, 102, 183, 24, 
                          120, 19, 123, 2, 17, 226, 11, 211, 25, 191, 205, 77]
Dim siStart As Short
Dim siGap As Short = siToSort.Max
Dim bSorting, bGap1 As Boolean
 
Print "To sort: -"
ShowWorking(siToSort)
Print
 
Repeat
  bSorting = False
  siStart = 0
  If siGap = 1 Then bGap1 = True

  Repeat
    If siToSort[siStart] > siToSort[siStart + siGap] Then 
      Swap siToSort[siStart], siToSort[siStart + siGap]
      bSorting = True
    End If
    Inc siStart
  Until siStart + siGap > siToSort.Max

  If bSorting Then ShowWorking(siToSort)
  siGap /= 1.3
  If siGap < 1 Then siGap = 1
  
Until bSorting = False And bGap1 = True
 
End
'-----------------------------------------
Public Sub ShowWorking(siToSort As Short[])
Dim siCount As Short

For siCount = 0 To siToSort.Max
  Print Str(siToSort[siCount]);
  If siCount <> siToSort.Max Then Print ",";
Next

Print

End

Output:

To sort: -
249,28,111,36,171,98,29,448,44,147,154,46,102,183,24,120,19,123,2,17,226,11,211,25,191,205,77

77,28,111,36,171,98,29,448,44,147,154,46,102,183,24,120,19,123,2,17,226,11,211,25,191,205,249
77,11,111,25,171,98,29,448,44,147,154,46,102,183,24,120,19,123,2,17,226,28,211,36,191,205,249
77,11,111,2,17,98,28,211,36,147,154,46,102,183,24,120,19,123,25,171,226,29,448,44,191,205,249
46,11,111,2,17,19,28,25,36,147,29,77,44,183,24,120,98,123,211,171,226,154,448,102,191,205,249
36,11,29,2,17,19,24,25,46,123,111,77,44,154,28,102,98,147,211,171,226,183,448,120,191,205,249
24,11,29,2,17,19,36,25,28,102,98,77,44,154,46,123,111,120,191,171,226,183,448,147,211,205,249
17,11,29,2,24,19,36,25,28,102,46,77,44,120,98,123,111,154,191,147,211,183,249,171,226,205,448
2,11,19,17,24,28,36,25,29,44,46,77,102,111,98,123,120,154,183,147,171,191,205,211,226,249,448
2,11,19,17,24,25,29,28,36,44,46,77,98,111,102,123,120,147,171,154,183,191,205,211,226,249,448
2,11,17,19,24,25,28,29,36,44,46,77,98,102,111,120,123,147,154,171,183,191,205,211,226,249,448

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
        }
    }
}

More generic version that sorts anything that implements sort.Interface:

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
        }
    }
}

Groovy

Combsort solution:

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
}

Combsort11 solution:

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
}

Test:

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]))

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

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

Example:

*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]

Haxe

class CombSort {
  @:generic
  public static function sort<T>(arr:Array<T>) {
    var gap:Float = arr.length;
    var swaps = true;
    while (gap > 1 || swaps) {
      gap /= 1.247330950103979;
      if (gap < 1) gap = 1.0; 
      var i = 0;
      swaps = false;
      while (i + gap < arr.length) {
        var igap = i + Std.int(gap);
        if (Reflect.compare(arr[i], arr[igap]) > 0) {
          var temp = arr[i];
          arr[i] = arr[igap];
          arr[igap] = temp;
          swaps = true;
        }
        i++;
      }
    }
  }
}

class Main {
  static function main() {
    var integerArray   = [1, 10, 2, 5, -1, 5, -19, 4, 23, 0];
    var floatArray = [1.0, -3.2, 5.2, 10.8, -5.7, 7.3, 
                      3.5, 0.0, -4.1, -9.5];
    var stringArray = ['We', 'hold', 'these', 'truths', 'to', 
                       'be', 'self-evident', 'that', 'all', 
                       'men', 'are', 'created', 'equal'];
    Sys.println('Unsorted Integers: ' + integerArray);
    CombSort.sort(integerArray);
    Sys.println('Sorted Integers:   ' + integerArray);
    Sys.println('Unsorted Floats:   ' + floatArray);
    CombSort.sort(floatArray);
    Sys.println('Sorted Floats:     ' + floatArray);
    Sys.println('Unsorted Strings:  ' + stringArray);
    CombSort.sort(stringArray);
    Sys.println('Sorted Strings:    ' + stringArray);
  }
}
Output:
Unsorted Integers: [1,10,2,5,-1,5,-19,4,23,0]
Sorted Integers:   [-19,-1,0,1,2,4,5,5,10,23]
Unsorted Floats:   [1,-3.2,5.2,10.8,-5.7,7.3,3.5,0,-4.1,-9.5]
Sorted Floats:     [-9.5,-5.7,-4.1,-3.2,0,1,3.5,5.2,7.3,10.8]
Unsorted Strings:  [We,hold,these,truths,to,be,self-evident,that,all,men,are,created,equal]
Sorted Strings:    [We,all,are,be,created,equal,hold,men,self-evident,that,these,to,truths]

Icon and Unicon

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

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)

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)

IS-BASIC

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

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.

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
)

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.

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;
            }
        }
    }
}

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);
}


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

jq

Works with: jq version 1.4

An implementation of the pseudo-code in the task description:

# 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] ;

Julia

# v0.6

function combsort!(x::Array)::Array
    gap, swaps = length(x), true
    while gap > 1 || swaps
        gap = floor(Int, gap / 1.25)
        i, swaps = 0, false
        while i + gap < length(x)
            if x[i+1] > x[i+1+gap]
                x[i+1], x[i+1+gap] = x[i+1+gap], x[i+1]
                swaps = true
            end
            i += 1
        end
    end
    return x
end

x = randn(100)
@show x combsort!(x)
@assert issorted(x)
Output:
x = [1.41167, 1.19626, 0.821703, 0.336024, -0.708447, 0.694578, 1.49075, -1.07124, -1.59686, -0.720135]
combsort!(x) = [-1.59686, -1.07124, -0.720135, -0.708447, 0.336024, 0.694578, 0.821703, 1.19626, 1.41167, 1.49075]

Kotlin

// version 1.1.2

fun <T : Comparable<T>> combSort(input: Array<T>) {
    var gap = input.size
    if (gap <= 1) return  // already sorted
    var swaps = false
    while (gap > 1 || swaps) {
        gap = (gap / 1.247331).toInt()
        if (gap < 1) gap = 1
        var i = 0
        swaps = false
        while (i + gap < input.size) {
            if (input[i] > input[i + gap]) {
                val tmp = input[i]
                input[i] = input[i + gap]
                input[i + gap] = tmp
                swaps = true 
            }
            i++
        }
    }
}  
 
fun main(args: Array<String>) {
    val ia = arrayOf(28, 44, 46, 24, 19, 2, 17, 11, 25, 4)
    println("Unsorted : ${ia.contentToString()}") 
    combSort(ia)
    println("Sorted   : ${ia.contentToString()}") 
    println()
    val ca = arrayOf('X', 'B', 'E', 'A', 'Z', 'M', 'S', 'L', 'Y', 'C')
    println("Unsorted : ${ca.contentToString()}") 
    combSort(ca)
    println("Sorted   : ${ca.contentToString()}") 
}
Output:
Unsorted : [28, 44, 46, 24, 19, 2, 17, 11, 25, 4]
Sorted   : [2, 4, 11, 17, 19, 24, 25, 28, 44, 46]

Unsorted : [X, B, E, A, Z, M, S, L, Y, C]
Sorted   : [A, B, C, E, L, M, S, X, Y, Z]

Liberty BASIC

'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

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}))

Maple

swap := proc(arr, a, b)
	local temp;
	temp := arr[a]:
	arr[a] := arr[b]:
	arr[b] := temp:
end proc:
newGap := proc(gap)
	local new;
	new := trunc(gap*10/13);
	if (new < 1) then return 1; end if;
	return new;
end proc;
combsort := proc(arr, len)
	local gap, swapped,i, temp;
	swapped := true:
	gap := len:
	while ((not gap = 1) or swapped) do
		gap := newGap(gap):
		swapped := false:
		for i from 1 to len-gap by 1 do
			if (arr[i] > arr[i+gap]) then
				temp := arr[i]:
				arr[i] := arr[i+gap]:
				arr[i+gap] := temp:
				swapped:= true:
			end if:
		end do:
	end do:
end proc:
arr := Array([17,3,72,0,36,2,3,8,40,0]);
combsort(arr, numelems(arr));
arr;
Output:
[0,0,2,3,3,8,17,36,40,72]

Mathematica /Wolfram Language

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[ list[[i]] > list[[i + gap]], swaps = True;
                list[[i ;; i + gap]] = list[[i + gap ;; i ;; -1]];  
                ];
            i++; 
            ]
        ]   
]
combSort@{2, 1, 3, 7, 6}
->{1, 2, 3, 6, 7}

MATLAB / Octave

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

Sample Output:

>> combSort([4 3 1 5 6 2])

ans =

     1     2     3     4     5     6

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
)

Output:

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)

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
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

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

Output:

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

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;
        };
      };
    }  
  }
}

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
;;

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}}

PARI/GP

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
};

Pascal

program CombSortDemo;


// NOTE: The array is 1-based
//       If you want to use this code on a 0-based array, see below
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.

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
program CombSortDemo;


// NOTE: The array is 0-based
//       If you want to use this code on a 1-based array, see above
type
  TIntArray = array[0..39] 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 := 0 to length(a) - gap - 1 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.

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;
}

Phix

with javascript_semantics

function comb_sort(sequence s)
integer gap = length(s)-1
    while 1 do
        gap = max(floor(gap/1.3),1)
        integer swapped = 0
        for i=1 to length(s)-gap do
            object si = s[i]
            if si>s[i+gap] then
                s[i] = s[i+gap]
                s[i+gap] = si
                swapped = 1
            end if
        end for
        if gap=1 and swapped=0 then exit end if
    end while
    return s
end function

?comb_sort(shuffle(tagset(10)))
Output:
{1,2,3,4,5,6,7,8,9,10}

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;
}

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 )

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

/* 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;

PowerShell

Massaging gap to always hit 11. Based on PowerShell from Cocktail Sort

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 ) } )

PureBasic

Implementation of CombSort11.

;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

Implementation of CombSort.

;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

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]
>>>

R

comb.sort<-function(a){
  gap<-length(a)
  swaps<-1
  while(gap>1 & swaps==1){
    gap=floor(gap/1.3)
    if(gap<1){
      gap=1
      }
    swaps=0
    i=1
    while(i+gap<=length(a)){
        if(a[i]>a[i+gap]){
        a[c(i,i+gap)] <- a[c(i+gap,i)]
        swaps=1
        }
        i<-i+1
      }
  }  
  return(a) 
}

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)

Raku

(formerly Perl 6)

Translation of: Perl
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';

REXX

/*REXX program  sorts  and displays  a  stemmed array  using the  comb sort  algorithm. */
call gen                                         /*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 (with # entries)*/
call show    ' after sort'                       /*display the   after  array elements. */
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
combSort: procedure expose @.;   parse arg N     /*N:  is the number of  @  elements.   */
          g= N-1                                 /*G:  is the gap between the sort COMBs*/
                 do  until g<=1 & done;  done= 1 /*assume sort is done  (so far).       */
                 g= g * 0.8  % 1                 /*equivalent to:   g= trunc( g / 1.25) */
                 if g==0  then g= 1              /*handle case of the gap is too small. */
                    do j=1  until $>=N;  $= j+g  /*$:     a temporary index  (pointer). */
                    if @.j>@.$  then do;   _= @.j;    @.j= @.$;   @.$= _;   done= 0;   end
                    end   /*j*/
                 end     /*until*/               /* [↑]  swap two elements in the array.*/
          return
/*──────────────────────────────────────────────────────────────────────────────────────*/
gen: @.=;     @.1  = '----polygon---  sides'  ;              @.12 = "dodecagon         12"
              @.2  = '============== =======' ;              @.13 = "tridecagon        13"
              @.3  = 'triangle           3'   ;              @.14 = "tetradecagon      14"
              @.4  = 'quadrilateral      4'   ;              @.15 = "pentadecagon      15"
              @.5  = 'pentagon           5'   ;              @.16 = "hexadecagon       16"
              @.6  = 'hexagon            6'   ;              @.17 = "heptadecagon      17"
              @.7  = 'heptagon           7'   ;              @.18 = "octadecagon       18"
              @.8  = 'octagon            8'   ;              @.19 = "enneadecagon      19"
              @.9  = 'nonagon            9'   ;              @.20 = "icosagon          20"
              @.10 = 'decagon           10'   ;              @.21 = "hectogon         100"
              @.11 = 'hendecagon        11'   ;              @.22 = "chiliagon       1000"
                                                             @.23 = "myriagon       10000"
                         do #=1  while  @.#\=='';  end    /*find how many elements in @ */
      #= #-1;     w= length(#);           return          /*adjust # because of DO loop.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show:     do k=1  for #; say right('element',15) right(k,w)  arg(1)":"  @.k;  end;  return

Data trivia:   A   hendecagon   (also known as an   undecagon   or   unidecagon)   is from the Greek word   hendeka   [eleven]   and   gon─   [corner].

output:

(Shown at three-quarter size.)

        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

Ring

aList = [3,5,1,2,7,4,8,3,6,4,1]
see combsort(aList)

func combsort t
     gapd = 1.2473
     gap =  len(t)
     swaps = 0
     while gap + swaps > 1 
           k = 0
           swaps = 0
           if gap > 1 gap = floor(gap / gapd) ok
           for k = 1 to len(t) - gap 
               if t[k] > t[k + gap] 
                  temp = t[k]
                  t[k] = t[k + gap]
                  t[k + gap] = temp
                  swaps = swaps + 1 ok
           next
     end
        return t

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!

results in

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

Rust

fn comb_sort<T: PartialOrd>(a: &mut [T]) {
    let len = a.len();
    let mut gap = len;
    let mut swapped = true;
    while gap > 1 || swapped {
        gap = (4 * gap) / 5;
        if gap < 1 {
            gap = 1;
        }
        let mut i = 0;
        swapped = false;
        while i + gap < len {
            if a[i] > a[i + gap] {
                a.swap(i, i + gap);
                swapped = true;
            }
            i += 1;
        }
    }
}

fn main() {
    let mut v = vec![10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6];
    println!("before: {:?}", v);
    comb_sort(&mut v);
    println!("after:  {:?}", v);
}
Output:
before: [10, 8, 4, 3, 1, 9, 0, 2, 7, 5, 6]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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;

Scala

Imperative version (Ugly, side effects)

object CombSort extends App {
  val ia = Array(28, 44, 46, 24, 19, 2, 17, 11, 25, 4)
  val ca = Array('X', 'B', 'E', 'A', 'Z', 'M', 'S', 'L', 'Y', 'C')

  def sorted[E](input: Array[E])(implicit ord: Ordering[E]): Array[E] = {
    import ord._
    var gap = input.length
    var swapped = true
    while (gap > 1 || swapped) {
      if (gap > 1) gap = (gap / 1.3).toInt
      swapped = false
      for (i <- 0 until input.length - gap)
        if (input(i) >= input(i + gap)) {
          val t = input(i)
          input(i) = input(i + gap)
          input(i + gap) = t
          swapped = true
        }
    }
    input
  }

  println(s"Unsorted : ${ia.mkString("[", ", ", "]")}")
  println(s"Sorted   : ${sorted(ia).mkString("[", ", ", "]")}\n")

  println(s"Unsorted : ${ca.mkString("[", ", ", "]")}")
  println(s"Sorted   : ${sorted(ca).mkString("[", ", ", "]")}")

}
Output:

See it in running in your browser by ScalaFiddle (JavaScript) or by Scastie (JVM).

Sidef

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;
        for i in ^(arr.len - gap) {
            if (arr[i] > arr[i+gap]) {
                arr[i, i+gap] = arr[i+gap, i];
                swaps = true;
            }
        }
    }
    return arr;
}

Swift

Translation of: C
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
            }
        }
    }
}

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]

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.

:L1→L2
:dim(L2)→A
:While A>5 and B=0
:int(A/1.3)→A
:1→C
:0→B
:While (C+A)≥dim(L2)
:If L2(C)>L2(C+A)
:Then
:L2(C)→D
:L2(C+A)→L2(C)
:D→L2(C+A)
:1→B
:End
:C+1→C
:End
:DelVar A
:DelVar B
:DelVar C
:DelVar D
:L1→L3
:L2→L1
:prgmSORTINS
:L3→L1
:DelVar L3
:Return

uBasic/4tH

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

VBA

{[trans|Phix}}

Function comb_sort(ByVal s As Variant) As Variant
    Dim gap As Integer: gap = UBound(s)
    Dim swapped As Integer
    Do While True
        gap = WorksheetFunction.Max(WorksheetFunction.Floor_Precise(gap / 1.3), 1)
        swapped = False
        For i = 0 To UBound(s) - gap
            si = Val(s(i))
            If si > Val(s(i + gap)) Then
                s(i) = s(i + gap)
                s(i + gap) = CStr(si)
                swapped = True
            End If
        Next i
        If gap = 1 And Not swapped Then Exit Do
    Loop
    comb_sort = s
End Function

Public Sub main()
    Dim s(9) As Variant
    For i = 0 To 9
        s(i) = CStr(Int(1000 * Rnd))
    Next i
    Debug.Print Join(s, ", ")
    Debug.Print Join(comb_sort(s), ", ")
End Sub
Output:
45, 414, 862, 790, 373, 961, 871, 56, 949, 364
45, 56, 364, 373, 414, 790, 862, 871, 949, 961

V (Vlang)

Translation of: go
fn main() {
    mut a := [170, 45, 75, -90, -802, 24, 2, 66]
    println("before: $a")
    comb_sort(mut a)
    println("after: $a")
}
 
fn comb_sort(mut a []int) {
    if a.len < 2 {
        return
    }
    for gap := a.len; ; {
        if gap > 1 {
            gap = gap * 4 / 5
        }
        mut 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 >= a.len {
                break
            }
        }
        if gap == 1 && !swapped {
            break
        }
    }
}

Wren

var combSort = Fn.new { |a|
    var gap = a.count
    while (true) {
        gap = (gap/1.25).floor
        if (gap < 1) gap = 1
        var i = 0
        var swaps = false
        while (true) {
            if (a[i] > a[i+gap]) {
                var t = a[i]
                a[i] = a[i+gap]
                a[i+gap] = t
                swaps = true
            }
            i = i + 1
            if (i + gap >= a.count) break
        }
        if (gap == 1 && !swaps) return
    }
}

var array = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
for (a in array) {
    System.print("Before: %(a)")
    combSort.call(a)
    System.print("After : %(a)")
    System.print()
}
Output:
Before: [4, 65, 2, -31, 0, 99, 2, 83, 782, 1]
After : [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782]

Before: [7, 5, 2, 6, 1, 4, 2, 6, 3]
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]

XPL0

Translation of: ALGOL W
    \Comb sorts in-place the array of integers Input with bounds LB :: UB
    procedure CombSort ( Input, LB, UB );
    integer   Input, LB, UB;
    integer   InputSize, Gap, I, Swapped, T, IGap;
    begin
        InputSize := ( UB - LB ) + 1;
        if InputSize > 1 then begin
            \more than one element, so must sort
            Gap     := InputSize; \initial Gap is the whole array size
            Swapped := true;
            while Gap # 1 or Swapped do begin
                \update the Gap value for a next comb
                Gap := fix( Floor(float(Gap) / 1.25) );
                if Gap < 1 then begin
                    \ensure the Gap is at least 1
                    Gap := 1
                end; \if_Gap_lt_1
                Swapped := false;
                \a single "comb" over the input list
                I := LB;
                while I + Gap <= UB do begin
                    T    := Input( I );
                    IGap := I + Gap;
                    if T > Input( IGap ) then begin
                        \need to swap out-of-order items
                        Input( I    ) := Input( IGap );
                        Input( IGap ) := T;
                        \Flag a swap has occurred, so the list is not guaranteed sorted yet
                        Swapped := true 
                    end; \if_t_gt_input__iGap
                    I := I + 1
                end \while_I_plus_Gap_le_UB
            end \while_Gap_ne_1_or_swapped
        end \if_inputSize_gt_1
    end; \combSort

        integer Data, I;
    begin \test
        Data:= [0, 9, -4, 0, 2, 3, 77, 1];
        for I := 1 to 7 do begin Text(0, " ");  IntOut(0, Data( I ) ) end;
        CombSort( Data, 1, 7 );
        Text(0, ( " -> " ) );
        for I := 1 to 7 do begin Text(0, " ");  IntOut(0, Data( I ) ) end;
    end
Output:
 9 -4 0 2 3 77 1 ->  -4 0 1 2 3 9 77

zkl

Translation of: D
fcn combSort(list){
   len,gap,swaps:=list.len(),len,True;
   while(gap>1 or swaps){
      gap,swaps=(1).max(gap.toFloat()/1.2473), False;
      foreach i in (len - gap){
         if(list[i]>list[i + gap]){
	    list.swap(i,i + gap);
	    swaps=True;
	 }
      }
   }
   list
}
combSort(List(28, 44, 46, 24, 19, 2, 17, 11, 25, 4)).println();
combSort("This is a test".toData()).text.println();
Output:
L(2,4,11,17,19,24,25,28,44,46)
   Taehiissstt