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

 

int gap = input.length;

bool swaps = true;

while (gap > 1 || swaps) {

swaps = false;

if (input[i] > input[i + gap]) {

swaps = true;

}

 

void main() {

 

=={{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|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:

 

 

 

 

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

end

}

return X

 

 

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)</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|Lua}}==

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

while gap + swaps > 1 do

end

 

 

listSize = numel(list);

end %while

end %while

 

Sample Output:

 

ans =

 

 

=={{header|OCaml}}==

 

let input_length = Array.length input in

let gap = ref(input_length) in

gap := int_of_float (float !gap /. 1.3);

 

swapped := false;

swapped := true;

done

done

 

=={{header|Oz}}==

proc {CombSort Arr}

Low = {Array.low Arr}

in

{CombSort Arr}

=={{header|PHP}}==

$gap = count($arr);

while ($gap > 1 || $swap){

if($gap > 1) $gap /= 1.25;

}

return $arr;

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

/* From the pseudocode. */

comb_sort: procedure (A);

end;

end comb_sort;

 

=={{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|Ruby}}==

def combsort!

gap = size

swaps = true

swaps = false

0.upto(size - gap - 1) do |i|

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.

:DelVar L₃

:Return