combsort

Är i skrivande stund för trött att gå igenom koden... hittade dock nedan länk, vars kod ser mer effektiv ut (inga floats). Lite fulkod (;; och break) var det ändock, men det kan du ju lätt göra om ;)

http://yagni.com/combsort/index.php

hmm inte min starka sida....

Vilket? Nedan kod funkar iaf:

#include <iostream>

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

static void combsort(int a[], int aSize) {
  int gap = aSize;
  bool run = true;
  do{
    gap = newGap(gap);
    bool swapped = false;
    for (int i = 0; i < aSize - gap; i++) {
      int j = i + gap;
      if (a[i] > a[j]) {
        std::swap(a[i], a[j]);
        swapped = true;
      }
    }
    if (gap == 1 && !swapped)
      run = false;
  }while(run);
}

int main() {

	int i,a[10]={10,9,8,7,6,5,4,3,2,1};

	std::cout<<"Array initialized with: ";
	for(i=0;i<10;i++)
		std::cout << a[i] << " ";

	combsort(a,10);
	std::cout << "\n\ncombsort!" << std::endl;

	std::cout << "\nNow array is like this: ";
	for(i=0;i<10;i++)
		std::cout << a[i] << " ";
    

  return 0;
}

yepp!

nån som vet vad denna kodsnutt har för funktion?

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

http://yagni.com/combsort/index.php

C++ combsort sorts 10,000 items in 0.0042 seconds, only 1.1 times longer than C++ quicksort. It's amazing that such a simple change to bubblesort makes it nearly as good as quicksort. What's more, combsort doesn't need any special code to keep from degenerating in the presence of already sorted lists.

Combsort starts out comparing items that are far apart. Then it makes the gap smaller and does it again. In the algorithm's last passes the gap is 1, making it act identical to bubblesort. That makes it easy to see that this algorithm is correct, since we know that bubblesort is correct and this algorithm always turns into bubblesort.

The newGap function contains some magic spells. Stepehn Lacey and Richard Box showed that the gap should be divided by 1.3 on each pass. They also found that gaps of 9 and 10 are bad and are best replaced with a gap of 115. (Further research by Jim Veale suggests that a carefully made table of gaps can improve performance further6).

Mao... algoritmen håller reda på avstånden mellan vissa element och man kan korta ned antalet byten genom att inte byta i onödan. (Vilket är en av akilleshälarna med Bubblesort).

Som implementation ser jag ingen fördel med combsort mot den effektivare quicksort (som f.ö finns färdigt i de flesta språk via std-lib).