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