# Algorithm Implementation/Sorting/Comb sort

## Java

```public static int[] sortArray(int[] arr){
double shrinkFactor = 1.3;
if(arr.length >0){
double gap = (arr.length-1)/ shrinkFactor;

while(gap>1){
int i = 0;
int j = (int) (i+ Math.floor(gap));
while(j != arr.length){
if(arr[i]> arr[j]){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
}
i++;
j++;
}
gap =gap/ shrinkFactor;
}
}
return arr;
}
```

## C++

```int newGap(int gap){
gap /= 1.3;
if(gap == 9 || gap == 10)
gap = 11;
if(gap < 1)
return 1;
return gap;
}

void combSort(int a[], int len){
int gap = len;
bool swapped;
do{
swapped = false;
gap = newGap(gap);
for(int i=0; i < len-gap; ++i){
if(a[i] > a[i+gap]){
swapped = true;
swap(a[i], a[i+gap]);
}
if(a[i] == a[i+gap]){
swapped = true;
}
}
}while(gap > 1 || swapped);
}
```

## C

```void comb_sort(int *input, size_t size) {
const float shrink = 1.3f;
int swap;
size_t i, gap = size;
bool swapped = false;

while ((gap > 1) || swapped) {
if (gap > 1) {
gap = (size_t)((float)gap / shrink);
}

swapped = false;

for (i = 0; gap + i < size; ++i) {
if (input[i] > input[i + gap]) {
swap = input[i];
input[i] = input[i + gap];
input[i + gap] = swap;
swapped = true;
}
if (input[i] == input[i + gap]) {
swapped = true;
}
}
}
}
```

Comb Sort 11 [1]

```void comb_sort11(int *input, size_t size)
{ int i,j,top,tmp,switched=0,gap=size;
if (7==gap) gap=8;  //optional line - improves single case
while (1<gap || switched)
{	if ((gap=(size_t)(gap*49L/64)) < 11)  // *49/64 approximates /1.3
if (9<=gap) gap=11;
else if (!gap) gap=1;
for (switched=0,	top=size-gap, i=0;i<top;++i)
{	j=i+gap;
if (input[i]<input[j])
{ tmp=input[i]; input[i]=input[j]; input[j]=tmp; switched=1; }	//swap
}	}
}
```

Comb Sort 9

```//comb_sort9 is a stripped combsort(tested OK for ALL permutations of size 0-9)
// in the applicable range, this sort has tiny code and excellent performance
//comparison/conditonal swaps approximate:
// (n*n+n)/2-(-1.314286 - 0.7285714*n + 0.2142857*n*n) ;n=(size-1)
//                                 (* = need to use full combsort11 for this)
// size                 2	3	4	5	6	7	8	9	10*	11*	12*
// cmp/swap             1	3	6	9	14	19	24	29 36+n	42+n 49+n
// ceil(log2(size!))    1	3	5	7	10	13	16	19	22	26	29
//stripped combsort(tested OK for ALL permutations of size 0-9)
void comb_sort9(int *input, size_t size)
{	int i, j, tmp, top, gap=size;
assert(size<=9);	//ONLY for 9 entries or less
if (7==gap) gap=8;  //important line - required for this case
while (1<=(gap=(size_t)(gap*49L/64)))   // *49/64 approximates /1.3
{	for (top=size-gap, i=0; i<top; ++i)
{	j=i+gap;
if (input[i]<input[j])
{ tmp=input[i]; input[i]=input[j]; input[j]=tmp; }	//swap
}	}
}
```

## Perl

```sub comb_sort {
my @v = @_;
my \$max = scalar (@v);
my \$gap = \$max;
while (1) {
my \$swapped = 0;
\$gap = int (\$gap / 1.3);
\$gap = 11 if \$gap == 10 or \$gap == 9; # (optimization Combsort11)
\$gap = 1 if \$gap < 1;
my \$lmax = \$max - \$gap - 1;
foreach my \$i (0..\$lmax) {
(\$v[\$i], \$v[\$i+\$gap], \$swapped) = (\$v[\$i+\$gap], \$v[\$i], 1) if \$v[\$i] > \$v[\$i+\$gap];
}
last if \$gap == 1 and \$swapped == 0;
}
return @v;
}
```

## Phix

```function comb_sort(sequence s)
integer gap = length(s)-1
while 1 do
gap = max(floor(gap/1.3),1)
integer swapped = 0
for i=1 to length(s)-gap do
object si = s[i]
if si>s[i+gap] then
s[i] = s[i+gap]
s[i+gap] = si
swapped = 1
end if
end for
if gap=1 and swapped=0 then exit end if
end while
return s
end function
```

## Python

```def update_gap(gap):
gap = (gap * 10) / 13
if gap == 9 or gap == 10:
gap = 11
return int(max(1, gap))

def combsort(x):
gap = len(x)
swapped = True
if gap < 2:
return
while gap > 1 or swapped:
gap = update_gap(gap)
swapped = False
for i in range(0, len(x) - gap):
if x[i] > x[i + gap]:
x[i], x[i + gap] = x[i + gap], x[i]
swapped = True
```

1. "A Fast Easy Sort", Byte Magazine, April 1991