Sorting algorithms/Comb sort: Difference between revisions

{{clarified-review}}

 

Variants:

 

Pseudocode:

'''function''' combsort('''array''' input)

'''end loop'''

'''end function'''

 

=={{header|ActionScript}}==

{

var gap:uint = input.length;

}

return input;

 

=={{header|Ada}}==

 

procedure Comb_Sort is

generic

end loop;

Ada.Text_IO.New_Line;

 

Output:

<pre>-1 0 1 3 3 4 256</pre>

 

=={{header|AutoHotkey}}==

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

 

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

Return, List

Message (1) box shows:

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

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

=={{header|AWK}}==

{

gap = len

for( i=0; i<length(a); i++ )

print a[i]

 

=={{header|BBC BASIC}}==

 

gap%=Size%

UNTIL gap%=1 AND Finished%

 

 

=={{header|C}}==

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

{

int i, j, gap, swapped = 1;

}

}

 

=={{header|C sharp|C#}}==

 

namespace CombSort

}

}

=={{header|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-000.

DISPLAY "SORT STARTING".

 

F-999.

=={{header|D}}==

{{trans|Python}}

 

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

data.combSort;

data.writeln;

{{out}}

<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>

=={{header|Eiffel}}==

class

feature

require

local

gap, i: INTEGER

shrink: REAL_64

do

from

until

loop

from

until

loop

end

end

end

end

 

end

end

Test:

class

APPLICATION

 

create

 

feature

 

end

{{out}}

<pre>

sorted:

-7 1 2 5 7 95 99

</pre>

 

=={{header|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 exchange

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

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

end subroutine combsort

=={{header|Go}}==

 

import "fmt"

}

}

 

More generic version that sorts anything that implements <code>sort.Interface</code>:

 

import (

}

}

 

=={{header|Groovy}}==

Combsort solution:

 

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

}

input

 

Combsort11 solution:

def swap = checkSwap.curry(input)

def size = input.size()

}

input

 

Test:

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

 

Output:

 

=={{header|Haskell}}==

import Control.Arrow

import Control.Monad

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

(\((_,xs),g) ->(gapSwapping g xs, fg g)) ((False,xs), fg $ length xs)

Example:

 

 

 

 

=={{header|Icon}} and {{header|Unicon}}==

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

end

}

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| 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.

on string : "qwerty"

with op = &null: "eqrtwy" (0 ms)</pre>

 

=={{header|J}}==

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.

 

gap=. #y

whilst.1 < gap+swaps do.

end.

y

 

Example use:

=={{header|Java}}==

This is copied from [[wp:Comb sort|the Wikipedia article]].

int gap = input.length;

boolean swapped = true;

}

}

=={{header|jq}}==

{{works with|jq|1.4}}

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

def combsort:

 

end)

| .[0] = $gap )

 

=={{header|Lua}}==

local gapd, gap, swaps = 1.2473, #t, 0

while gap + swaps > 1 do

end

 

 

gap = listSize = Length[list];

While[ !((gap <= 1) && (swaps == False)),

]

]

<pre>combSort@{2, 1, 3, 7, 6}

 

=={{header|MATLAB}} / {{header|Octave}}==

listSize = numel(list);

end %while

end %while

 

Sample Output:

 

ans =

 

 

=={{header|MAXScript}}==

(

local gap = arr.count

)

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)

 

=={{header|NetRexx}}==

 

options replace format comments java crossref savelog symbols binary

method isFalse public constant binary returns boolean

return \isTrue

;Output

<pre>

 

=={{header|Nim}}==

var gap = a.len

var swapped = true

swapped = false

var i = 0

if a[i] > a[j]:

swap a[i], a[j]

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

combSort a

Output:

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

 

=={{header|Objeck}}==

bundle Default {

class Stooge {

}

}

 

=={{header|OCaml}}==

 

let input_length = Array.length input in

let gap = ref(input_length) in

done

done

 

=={{header|Oz}}==

proc {CombSort Arr}

Low = {Array.low Arr}

in

{CombSort Arr}

=={{header|PARI/GP}}==

my(phi=(1+sqrt(5))/2,magic=1/(1-exp(-phi)),g=#v,swaps);

while(g>1 | swaps,

);

v

 

=={{header|Pascal}}==

 

type

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

end;

writeln;

Output:

<pre>

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

</pre>

 

=={{header|Perl}}==

my @arr = @_;

my $gap = @arr;

}

return @arr;

 

 

=={{header|PHP}}==

$gap = count($arr);

$swap = true;

}

return $arr;

 

=={{header|PicoLisp}}==

(let (Gap (length Lst) Swaps NIL)

(while (or (> Gap 1) Swaps)

(on Swaps) )

(pop 'Lst) ) ) ) )

Output:

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

 

=={{header|PL/I}}==

/* From the pseudocode. */

comb_sort: procedure (A);

end;

end comb_sort;

=={{header|PowerShell}}==

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

$l = $a.Length

$gap = 11

}

 

 

=={{header|PureBasic}}==

Implementation of CombSort11.

Procedure combSort11(Array a(1))

Protected i, gap, swaps = 1

Wend

Wend

Implementation of CombSort.

Procedure combSort(Array a(1))

Protected i, gap, swaps = 1

Wend

Wend

 

=={{header|Python}}==

gap = len(input)

swaps = True

>>> y

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

 

=={{header|Racket}}==

#lang racket

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

[swaps])))))

xs)

 

=={{header|REXX}}==

 

element 1 before sort: ----polygon--- sides

element 2 before sort: ============== =======

element 23 after sort: tridecagon 13

</pre>

 

=={{header|Ruby}}==

def combsort!

gap = size

end

 

results in

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

 

=={{header|Sather}}==

 

private swap(inout a, inout b:T) is

#OUT + b + "\n";

end;

 

=={{header|Tcl}}==

set gap [llength $input]

while 1 {

 

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

Produces this output:

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

=={{header|TI-83 BASIC}}==

Requires [[Insertion sort#TI-83 BASIC|prgmSORTINS]]. Gap division of 1.3. Switches to [[Insertion sort]] when gap is less than 5.

 

{{omit from|GUISS}}