Sorting algorithms/Comb sort
From Rosetta Code
< Sorting algorithms(Redirected from Comb sort)
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
Heapsort | Mergesort | Quicksort
O(n log2n) Sorts
Shell Sort
O(n2) Sorts
Bubble Sort | Cocktail Sort | Comb Sort | Gnome Sort | Insertion Sort | Selection Sort
Other Sorts
Bead Sort | Bogosort | Counting Sort | Pancake Sort | Permutation Sort | Stooge 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. See the article on Wikipedia.
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
Contents |
[edit] 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;
}
[edit] 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
[edit] 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
[edit] 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;
}
}
}
}
[edit] 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;
}
}
}
}
[edit] 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;
}
}
}
[edit] 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.
[edit] D
Works with: D version 2
Translation of: Python
import std.algorithm, std.stdio;
void combsort(T)(T[] input) {
int gap = input.length;
bool swaps = true;
while (gap > 1 || swaps) {
gap = max(1, cast(int)(gap / 1.2473)); // minimum gap is 1
swaps = false;
foreach (i; 0 .. input.length - gap)
if (input[i] > input[i + gap]) {
swap(input[i], input[i + gap]);
swaps = true;
}
}
}
void main() {
auto a = [88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70];
combsort(a);
assert(a == a.dup.sort);
writeln(a);
}
[edit] 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
[edit] 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]
[edit] 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)
[edit] 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.
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
[edit] 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;
}
}
}
}
[edit] 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}))
[edit] MATLAB
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
[edit] 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);
let i = ref 0 in
swapped := false;
while (!i + !gap < input_length) 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;
incr i;
done
done
;;
[edit] 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}}
[edit] PHP
function combSort($arr){
$gap = count($arr);
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;
}
[edit] 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;
[edit] 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
[edit] 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]
>>>
[edit] Ruby
class Array
def combsort!
gap = size
swaps = true
until gap <= 1 and swaps
gap = (gap / 1.25).to_int
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]
[edit] 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;
[edit] 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
[edit] 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
Categories: Clarified and Needing Review | Programming Tasks | Sorting Algorithms | ActionScript | AutoHotkey | BBC BASIC | C | C++ | C sharp | COBOL | D | Forth | Haskell | Io | J | Java | Lua | MATLAB | OCaml | Oz | PHP | PL/I | PureBasic | Python | Ruby | Sather | Tcl | TI-83 BASIC
