Sorting algorithms/Comb sort: Difference between revisions

{{trans|Python}}

 

V gap = input.len

V swaps = 1B

combsort(&y)

assert(y == sorted(y))

 

{{out}}

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

YREGS

RI EQU 6 i

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program combSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|Action!}}==

INT i

 

Test(c,8)

Test(d,12)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Comb_sort.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

var gap:uint = input.length;

}

return input;

 

=={{header|Ada}}==

 

procedure Comb_Sort is

generic

end loop;

Ada.Text_IO.New_Line;

 

Output:

=={{header|ALGOL 68}}==

{{libheader|ALGOL 68-rows}}

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 #

print( ( " -> " ) );

SHOW data

{{out}}

<pre>

=={{header|ALGOL W}}==

{{Trans|ALGOL 68}}

% comb-sorts in-place the array of integers input with bounds lb :: ub %

procedure combSort ( integer array input ( * )

for i := 1 until 7 do writeon( i_w := 1, s_w := 0, " ", data( i ) )

end

{{out}}

<pre>

 

=={{header|AppleScript}}==

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

 

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.

 

{{output}}

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program combSort.s */

/***************************************************/

.include "../affichage.inc"

=={{header|Arturo}}==

 

a: new items

gap: size a

]

 

 

{{out}}

 

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

 

=={{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|C++}}==

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

void combsort ( ForwardIterator first, ForwardIterator last )

{

}

}

 

=={{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|Common Lisp}}==

 

(defun comb-sort (input)

(setf swapped t))

while (or (> gap 1) swapped)

 

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

{{libheader| System.Types}}

'''Adaptation of Pascal'''

program Comb_sort;

 

 

Readln;

{{out}}

<pre>

</pre>

=={{header|Eiffel}}==

 

class

end

 

Test:

class

APPLICATION

 

end

{{out}}

<pre>

=={{header|Elena}}==

ELENA 5.0 :

import system'math;

import system'routines;

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.combSort().asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def comb_sort([]), do: []

def comb_sort(input) do

end

 

 

{{out}}

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

 

===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 for clarity

UNTIL

DROP

 

=={{header|Fortran}}==

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

implicit none

end subroutine combsort

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundary checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>normal comb sort

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

Print

 

Output:

<pre>

 

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

@:generic

public static function sort<T>(arr:Array<T>) {

Sys.println('Sorted Strings: ' + stringArray);

}

 

{{out}}

 

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

 

=={{header|Io}}==

combSortInPlace := method(

gap := size

 

lst := list(23, 76, 99, 58, 97, 57, 35, 89, 51, 38, 95, 92, 24, 46, 31, 24, 14, 12, 57, 78)

 

=={{header|IS-BASIC}}==

110 RANDOMIZE

120 NUMERIC ARRAY(11 TO 30)

370 NEXT

380 LOOP

 

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

// Node 5.4.1 tested implementation (ES6)

function is_array_sorted(arr) {

// Print the sorted array

console.log(arr);

 

 

{{works with|jq|1.4}}

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

def combsort:

 

end)

| .[0] = $gap )

 

=={{header|Julia}}==

 

function combsort!(x::Array)::Array

x = randn(100)

@show x combsort!(x)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun <T : Comparable<T>> combSort(input: Array<T>) {

combSort(ca)

println("Sorted : ${ca.contentToString()}")

 

{{out}}

 

=={{header|Liberty BASIC}}==

'randomize 0.5

itemCount = 20

next i

end

 

=={{header|Lua}}==

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

while gap + swaps > 1 do

end

 

 

=={{header|Maple}}==

local temp;

temp := arr[a]:

arr := Array([17,3,72,0,36,2,3,8,40,0]);

combsort(arr, numelems(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)),

]

]

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

->{1, 2, 3, 6, 7}</pre>

 

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

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

 

 

end;

writeln;

Output:

<pre>

</pre>

 

 

 

end;

writeln;

 

=={{header|Perl}}==

my @arr = @_;

my $gap = @arr;

}

return @arr;

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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>

{{out}}

<pre>

 

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

comb.sort<-function(a){

gap<-length(a)

}

 

 

=={{header|Racket}}==

#lang racket

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

[swaps])))))

xs)

 

=={{header|Raku}}==

(formerly Perl 6)

{{trans|Perl}}

my $gap = +@a;

my $swaps = 1;

my @weights = (^50).map: { 100 + ( 1000.rand.Int / 10 ) };

say @weights.sort.Str eq @weights.&comb_sort.Str ?? 'ok' !! 'not ok';

 

=={{header|REXX}}==

call gen /*generate the @ array elements. */

call show 'before sort' /*display the before array elements. */

#= #-1; w= length(#); return /*adjust # because of DO loop.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

 

Data trivia: &nbsp; A &nbsp; ''hendecagon'' &nbsp; (also known as an &nbsp; ''undecagon'' &nbsp; or &nbsp; ''unidecagon'') &nbsp; is

 

=={{header|Ring}}==

aList = [3,5,1,2,7,4,8,3,6,4,1]

see combsort(aList)

end

return t

 

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

let len = a.len();

let mut gap = len;

comb_sort(&mut v);

println!("after: {:?}", v);

 

{{out}}

 

=={{header|Sather}}==

 

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

#OUT + b + "\n";

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

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;

}

return arr;

 

=={{header|Swift}}==

{{trans|C}}

var swapped = true

var gap = list.count

}

}

 

=={{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|uBasic/4tH}}==

n = FUNC (_InitArray)

PROC _ShowArray (n)

PRINT

 

=={{header|VBA}}==

Dim gap As Integer: gap = UBound(s)

Dim swapped As Integer

Debug.Print Join(s, ", ")

Debug.Print Join(comb_sort(s), ", ")

<pre>45, 414, 862, 790, 373, 961, 871, 56, 949, 364

45, 56, 364, 373, 414, 790, 862, 871, 949, 961</pre>

 

{{trans|go}}

mut a := [170, 45, 75, -90, -802, 24, 2, 66]

println("before: $a")

}

}

 

=={{header|Wren}}==

var gap = a.count

while (true) {

}

 

System.print("Before: %(a)")

combSort.call(a)

System.print("After : %(a)")

System.print()

 

{{out}}

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

</pre>

 

=={{header|zkl}}==

{{trans|D}}

len,gap,swaps:=list.len(),len,True;

while(gap>1 or swaps){

}

list

{{out}}

<pre>