Algorithm Implementation/Sorting/Comb sort

From Wikibooks, open books for an open world
Jump to: navigation, search

Python[edit]

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

Java[edit]

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++[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);
}

C[edit]

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

Comb Sort 11 [1]

void comb_sort11(int *input, size_t size)
{ int i,j,top,tmp,switched=0,gap=size;
  while (1<gap || switched)
  {	if ((gap=(size_t)((float)gap / 1.3f)) < 11)
  	  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

//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;
	while (1<=(gap=(size_t)((float)gap / 1.3f)))
	{	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[edit]

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;
}
  1. "A Fast Easy Sort", Byte Magazine, April 1991