Last modified on 18 July 2014, at 13:03

Algorithm Implementation/Sorting/Comb sort

PythonEdit

def update_gap(gap):
gap = (gap * 10) / 13
if gap == 9 or gap == 10:
gap = 11
return 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, gap):
if x[i] > x[i + gap]:
x[i], x[i + gap] = x[i + gap], x[i]
swapped = True

JavaEdit

private static int newGap(int gap)
{       gap = gap * 10 / 13;
if(gap == 9 || gap == 10)
gap = 11;
if(gap < 1)
return 1;
return gap;
}

private static void sort(int a[])
{       int gap = a.length;
boolean swapped;
do
{       swapped = false;
gap = newGap(gap);
for(int i = 0; i < (a.length - gap); i++)
{       if(a[i] > a[i + gap])
{       swapped = true;
int temp = a[i];
a[i] = a[i + gap];
a[i + gap] = temp;
}
}
} while(gap > 1 || swapped);
}

C++Edit

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]);
}
}
}while(gap > 1 || swapped);
}

CEdit

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

PerlEdit

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