Sorting algorithms/Comb sort: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (added Category:Sorting) |
m (→{{header|Wren}}: Minor tidy) |
||
(22 intermediate revisions by 15 users not shown) | |||
Line 51:
'''end function'''
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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)</syntaxhighlight>
{{out}}
<pre>
[0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
</pre>
=={{header|360 Assembly}}==
Translation from prototype.<br>
The program uses ASM structured macros and two ASSIST macros to keep the code as short as possible.
<
COMBSORT CSECT
USING COMBSORT,R13 base register
Line 122 ⟶ 147:
YREGS
RI EQU 6 i
END COMBSORT</
{{out}}
<pre>
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program combSort64.s */
Line 307 ⟶ 333:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Action!}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Comb_sort.png Screenshot from Atari 8-bit computer]
<pre>
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]
</pre>
=={{header|ActionScript}}==
<
{
var gap:uint = input.length;
Line 329 ⟶ 440:
}
return input;
}</
=={{header|Ada}}==
<
procedure Comb_Sort is
generic
Line 379 ⟶ 490:
end loop;
Ada.Text_IO.New_Line;
end Comb_Sort;</
Output:
<pre>-1 0 1 3 3 4 256</pre>
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-rows}}
<syntaxhighlight lang="algol68">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</syntaxhighlight>
{{out}}
<pre>
9 -4 0 2 3 77 1 -> -4 0 1 2 3 9 77
</pre>
=={{header|ALGOL W}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="algolw">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.</syntaxhighlight>
{{out}}
<pre>
9 -4 0 2 3 77 1 -> -4 0 1 2 3 9 77
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{output}}
<syntaxhighlight lang="applescript">{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}</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program combSort.s */
Line 548 ⟶ 849:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|AutoHotkey}}==
<
List2 = 88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70
Line 597 ⟶ 930:
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
Line 606 ⟶ 939:
=={{header|AWK}}==
<
{
gap = len
Line 643 ⟶ 976:
for( i=0; i<length(a); i++ )
print a[i]
}</
=={{header|BBC BASIC}}==
<
gap%=Size%
Line 665 ⟶ 998:
UNTIL gap%=1 AND Finished%
ENDPROC</
=={{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;
Line 692 ⟶ 1,025:
}
}
}</
=={{header|C sharp|C#}}==
<
namespace CombSort
Line 732 ⟶ 1,065:
}
}
}</
=={{header|C++}}==
This is copied from [[wp:Comb sort|the Wikipedia article]].
<
void combsort ( ForwardIterator first, ForwardIterator last )
{
Line 759 ⟶ 1,092:
}
}
}</
=={{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".
Line 803 ⟶ 1,136:
F-999.
EXIT.</
=={{header|Common Lisp}}==
<
(defun comb-sort (input)
Line 821 ⟶ 1,154:
(setf swapped t))
while (or (> gap 1) swapped)
finally (return input)))</
=={{header|D}}==
{{trans|Python}}
<
void combSort(T)(T[] input) pure nothrow @safe @nogc {
Line 846 ⟶ 1,179:
data.combSort;
data.writeln;
}</
{{out}}
<pre>[2, 4, 11, 17, 19, 24, 25, 28, 44, 46]</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.Types}}
'''Adaptation of Pascal'''
<syntaxhighlight lang="delphi">
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.</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
Line 924 ⟶ 1,364:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 959 ⟶ 1,399:
end
</syntaxhighlight>
{{out}}
<pre>
Line 970 ⟶ 1,410:
=={{header|Elena}}==
ELENA 5.0 :
<
import system'math;
import system'routines;
Line 1,011 ⟶ 1,451:
console.printLine("before:", list.asEnumerable());
console.printLine("after :", list.combSort().asEnumerable())
}</
{{out}}
<pre>
Line 1,019 ⟶ 1,459:
=={{header|Elixir}}==
<
def comb_sort([]), do: []
def comb_sort(input) do
Line 1,039 ⟶ 1,479:
end
(for _ <- 1..20, do: :rand.uniform(20)) |> IO.inspect |> Sort.comb_sort |> IO.inspect</
{{out}}
Line 1,049 ⟶ 1,489:
=={{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
Line 1,095 ⟶ 1,535:
: .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.
<
HEX
\ gratuitous variables
VARIABLE SORTED
DECIMAL
Line 1,110 ⟶ 1,549:
\ allocate a small array of cells
CREATE Q SIZE 2+ CELLS ALLOT
\ operator to index into the array
Line 1,116 ⟶ 1,555:
\ fill array and see array
: INITDATA ( -- ) SIZE 0 DO
: SEEDATA ( -- ) CR SIZE 0 DO I ]Q @ U. LOOP ;
\
\
:
: XCHG ( adr1 adr2 -- ) OVER @ OVER @ SWAP ROT ! SWAP ! ;
: COMBSORT ( n -- )
DUP
BEGIN
GAP
SORTED ON
DO
I GAP
IF
SORTED OFF \ flag we are not sorted
THEN
LOOP
SORTED @ GAP
UNTIL
DROP
;</syntaxhighlight>
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
<
implicit none
Line 1,192 ⟶ 1,625:
end subroutine combsort
end program Combsort_Demo</
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
' for boundary checks on array's compile with: fbc -s console -exx
Line 1,281 ⟶ 1,714:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>normal comb sort
Line 1,293 ⟶ 1,726:
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=ade780ac2893fcfc95bf0d3feff6a3a8 Click this link to run this code]'''
<
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]
Line 1,335 ⟶ 1,768:
Print
End</
Output:
<pre>
Line 1,354 ⟶ 1,787:
=={{header|Go}}==
<
import "fmt"
Line 1,388 ⟶ 1,821:
}
}
}</
More generic version that sorts anything that implements <code>sort.Interface</code>:
<
import (
Line 1,428 ⟶ 1,861:
}
}
}</
=={{header|Groovy}}==
Combsort solution:
<
def checkSwap = { a, i, j -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }
Line 1,447 ⟶ 1,880:
}
input
}</
Combsort11 solution:
<
def swap = checkSwap.curry(input)
def size = input.size()
Line 1,461 ⟶ 1,894:
}
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]))
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:
Line 1,479 ⟶ 1,912:
=={{header|Haskell}}==
<
import Control.Arrow
import Control.Monad
Line 1,491 ⟶ 1,924:
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:
<
[12,14,23,24,24,31,35,38,46,51,57,57,58,76,78,89,92,95,97,99]</
=={{header|Haxe}}==
<
@:generic
public static function sort<T>(arr:Array<T>) {
Line 1,539 ⟶ 1,972:
Sys.println('Sorted Strings: ' + stringArray);
}
}</
{{out}}
Line 1,552 ⟶ 1,985:
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(combsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 1,573 ⟶ 2,006:
}
return X
end</
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.
Line 1,585 ⟶ 2,018:
=={{header|Io}}==
<
combSortInPlace := method(
gap := size
Line 1,605 ⟶ 2,038:
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)</
=={{header|IS-BASIC}}==
<
110 RANDOMIZE
120 NUMERIC ARRAY(11 TO 30)
Line 1,637 ⟶ 2,070:
370 NEXT
380 LOOP
390 END DEF</
=={{header|J}}==
Line 1,643 ⟶ 2,076:
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.
Line 1,655 ⟶ 2,088:
end.
y
)</
Example use:
Line 1,665 ⟶ 2,098:
=={{header|Java}}==
This is copied from [[wp:Comb sort|the Wikipedia article]].
<
int gap = input.length;
boolean swapped = true;
Line 1,682 ⟶ 2,115:
}
}
}</
=={{header|JavaScript}}==
<
// Node 5.4.1 tested implementation (ES6)
function is_array_sorted(arr) {
Line 1,732 ⟶ 2,165:
// Print the sorted array
console.log(arr);
}</
Line 1,743 ⟶ 2,176:
{{works with|jq|1.4}}
An implementation of the pseudo-code in the task description:
<
def combsort:
Line 1,776 ⟶ 2,209:
end)
| .[0] = $gap )
| .[2] ;</
=={{header|Julia}}==
<
function combsort!(x::Array)::Array
Line 1,799 ⟶ 2,232:
x = randn(100)
@show x combsort!(x)
@assert issorted(x)</
{{out}}
Line 1,806 ⟶ 2,239:
=={{header|Kotlin}}==
<
fun <T : Comparable<T>> combSort(input: Array<T>) {
Line 1,839 ⟶ 2,272:
combSort(ca)
println("Sorted : ${ca.contentToString()}")
}</
{{out}}
Line 1,851 ⟶ 2,284:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'randomize 0.5
itemCount = 20
Line 1,890 ⟶ 2,323:
next i
end
</syntaxhighlight>
=={{header|Lua}}==
<
local gapd, gap, swaps = 1.2473, #t, 0
while gap + swaps > 1 do
Line 1,908 ⟶ 2,341:
end
print(unpack(combsort{3,5,1,2,7,4,8,3,6,4,1}))</
=={{header|Maple}}==
<
local temp;
temp := arr[a]:
Line 1,942 ⟶ 2,375:
arr := Array([17,3,72,0,36,2,3,8,40,0]);
combsort(arr, numelems(arr));
arr;</
{{Out|Output}}
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
gap = listSize = Length[list];
While[ !((gap <= 1) && (swaps == False)),
Line 1,961 ⟶ 2,394:
]
]
]</
<pre>combSort@{2, 1, 3, 7, 6}
->{1, 2, 3, 6, 7}</pre>
=={{header|MATLAB}} / {{header|Octave}}==
<
listSize = numel(list);
Line 1,997 ⟶ 2,428:
end %while
end %while
end %combSort</
Sample Output:
<
ans =
1 2 3 4 5 6</
=={{header|MAXScript}}==
<
(
local gap = arr.count
Line 2,034 ⟶ 2,465:
)
return arr
)</
Output:
<syntaxhighlight lang="maxscript">
a = for i in 1 to 10 collect random 1 10
#(2, 6, 5, 9, 10, 7, 2, 6, 1, 4)
combsort a
#(1, 2, 2, 4, 5, 6, 6, 7, 9, 10)
</syntaxhighlight>
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 2,095 ⟶ 2,526:
method isFalse public constant binary returns boolean
return \isTrue
</syntaxhighlight>
;Output
<pre>
Line 2,118 ⟶ 2,549:
=={{header|Nim}}==
<
var gap = a.len
var swapped = true
Line 2,127 ⟶ 2,558:
swapped = false
var i = 0
for j in gap ..
if a[i] > a[j]:
swap a[i], a[j]
Line 2,135 ⟶ 2,566:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
combSort a
echo a</
Output:
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|Objeck}}==
<
bundle Default {
class Stooge {
Line 2,174 ⟶ 2,605:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
<
let input_length = Array.length input in
let gap = ref(input_length) in
Line 2,196 ⟶ 2,627:
done
done
;;</
=={{header|Oz}}==
<
proc {CombSort Arr}
Low = {Array.low Arr}
Line 2,226 ⟶ 2,657:
in
{CombSort Arr}
{Show {Array.toRecord unit Arr}}</
=={{header|PARI/GP}}==
<
my(phi=(1+sqrt(5))/2,magic=1/(1-exp(-phi)),g=#v,swaps);
while(g>1 | swaps,
Line 2,244 ⟶ 2,675:
);
v
};</
=={{header|Pascal}}==
<
Line 2,299 ⟶ 2,730:
end;
writeln;
end.</
Output:
<pre>
Line 2,308 ⟶ 2,739:
</pre>
<
Line 2,360 ⟶ 2,791:
end;
writeln;
end.</
=={{header|Perl}}==
<
my @arr = @_;
my $gap = @arr;
Line 2,378 ⟶ 2,809:
}
return @arr;
}</
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">comb_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">gap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">/</span><span style="color: #000000;">1.3</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">swapped</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">gap</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">></span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">gap</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">si</span>
<span style="color: #000000;">swapped</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">gap</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">swapped</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">comb_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{1,2,3,4,5,6,7,8,9,10}
</pre>
=={{header|PHP}}==
<
$gap = count($arr);
$swap = true;
Line 2,417 ⟶ 2,858:
}
return $arr;
}</
=={{header|PicoLisp}}==
<
(let (Gap (length Lst) Swaps NIL)
(while (or (> Gap 1) Swaps)
Line 2,431 ⟶ 2,872:
(on Swaps) )
(pop 'Lst) ) ) ) )
Lst )</
Output:
<pre>: (combSort (88 18 31 44 4 0 8 81 14 78 20 76 84 33 73 75 82 5 62 70))
Line 2,437 ⟶ 2,878:
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
/* From the pseudocode. */
comb_sort: procedure (A);
Line 2,463 ⟶ 2,904:
end;
end comb_sort;
</syntaxhighlight>
=={{header|PowerShell}}==
Massaging gap to always hit 11. Based on PowerShell from [[Cocktail Sort]]
<
$l = $a.Length
$gap = 11
Line 2,497 ⟶ 2,938:
}
$l = 100; CombSort ( 1..$l | ForEach-Object { $Rand = New-Object Random }{ $Rand.Next( -( $l - 1 ), $l - 1 ) } )</
=={{header|PureBasic}}==
Implementation of CombSort11.
<
Procedure combSort11(Array a(1))
Protected i, gap, swaps = 1
Line 2,522 ⟶ 2,963:
Wend
Wend
EndProcedure</
Implementation of CombSort.
<
Procedure combSort(Array a(1))
Protected i, gap, swaps = 1
Line 2,543 ⟶ 2,984:
Wend
Wend
EndProcedure</
=={{header|Python}}==
<
gap = len(input)
swaps = True
Line 2,564 ⟶ 3,005:
>>> y
[0, 4, 5, 8, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
>>> </
=={{header|R}}==
<syntaxhighlight lang="r">
comb.sort<-function(a){
gap<-length(a)
Line 2,589 ⟶ 3,030:
}
</syntaxhighlight>
=={{header|Racket}}==
<
#lang racket
(require (only-in srfi/43 vector-swap!))
Line 2,611 ⟶ 3,052:
[swaps])))))
xs)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku"
my $gap = +@a;
my $swaps = 1;
Line 2,636 ⟶ 3,077:
my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) };
say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok';
</syntaxhighlight>
=={{header|REXX}}==
<
call gen /*generate the @ array elements. */
call show 'before sort' /*display the before array elements. */
Line 2,645 ⟶ 3,086:
call combSort # /*invoke the comb sort (with # entries)*/
call show ' after sort' /*display the after array elements. */
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
combSort: procedure expose @.; parse arg N /*N: is the number of @ elements. */
Line 2,673 ⟶ 3,114:
#= #-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
Line 2,732 ⟶ 3,173:
=={{header|Ring}}==
<
aList = [3,5,1,2,7,4,8,3,6,4,1]
see combsort(aList)
Line 2,753 ⟶ 3,194:
end
return t
</syntaxhighlight>
=={{header|Ruby}}==
<
def combsort!
gap = size
Line 2,774 ⟶ 3,215:
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
<pre>[12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]</pre>
=={{header|Rust}}==
<
let len = a.len();
let mut gap = len;
Line 2,805 ⟶ 3,246:
comb_sort(&mut v);
println!("after: {:?}", v);
}</
{{out}}
Line 2,814 ⟶ 3,255:
=={{header|Sather}}==
<
private swap(inout a, inout b:T) is
Line 2,850 ⟶ 3,291:
#OUT + b + "\n";
end;
end;</
=={{header|Scala}}==
===Imperative version (Ugly, side effects)===
<
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')
Line 2,882 ⟶ 3,323:
println(s"Sorted : ${sorted(ca).mkString("[", ", ", "]")}")
}</
{{Out}}See it in running in your browser by [https://scalafiddle.io/sf/7ykMPZx/0 ScalaFiddle (JavaScript)] or by [https://scastie.scala-lang.org/Gp1ZcxnPQAKvToWFZLU7OA Scastie (JVM)].
=={{header|Sidef}}==
<
var gap = arr.len;
var swaps = true;
Line 2,900 ⟶ 3,341:
}
return arr;
}</
=={{header|Swift}}==
{{trans|C}}
<
var swapped = true
var gap = list.count
Line 2,926 ⟶ 3,367:
}
}
}</
=={{header|Tcl}}==
<
set gap [llength $input]
while 1 {
Line 2,949 ⟶ 3,390:
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:
<pre>12 14 23 24 24 31 35 38 46 51 57 57 58 76 78 89 92 95 97 99</pre>
Line 2,985 ⟶ 3,426:
=={{header|uBasic/4tH}}==
<syntaxhighlight lang="text">PRINT "Comb sort:"
n = FUNC (_InitArray)
PROC _ShowArray (n)
Line 3,043 ⟶ 3,484:
PRINT
RETURN</
=={{header|VBA}}==
{[trans|Phix}}<
Dim gap As Integer: gap = UBound(s)
Dim swapped As Integer
Line 3,072 ⟶ 3,513:
Debug.Print Join(s, ", ")
Debug.Print Join(comb_sort(s), ", ")
End Sub</
<pre>45, 414, 862, 790, 373, 961, 871, 56, 949, 364
45, 56, 364, 373, 414, 790, 862, 871, 949, 961</pre>
=={{header|V (Vlang)}}==
{{trans|go}}
<syntaxhighlight lang="v (vlang)">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
}
}
}</syntaxhighlight>
=={{header|Wren}}==
<
var gap = a.count
while (true) {
Line 3,098 ⟶ 3,573:
}
var
for (a in
System.print("Before: %(a)")
combSort.call(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 3,114 ⟶ 3,589:
After : [1, 2, 2, 3, 4, 5, 6, 6, 7]
</pre>
=={{header|XPL0}}==
{{trans|ALGOL W}}
<syntaxhighlight lang "XPL0">
\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</syntaxhighlight>
{{out}}
<pre>
9 -4 0 2 3 77 1 -> -4 0 1 2 3 9 77</pre>
=={{header|zkl}}==
{{trans|D}}
<
len,gap,swaps:=list.len(),len,True;
while(gap>1 or swaps){
Line 3,129 ⟶ 3,655:
}
list
}</
<
combSort("This is a test".toData()).text.println();</
{{out}}
<pre>
|