Помогите с Сортировкой расчёской (Comb Sort)

[Dimasmir]

Подскажите, пожалуйста, где можно прочитать об этом методе сортировки по-русски или хотябы нормально по-английски и нормальный исходник сортировки.
Всё что смог найти непонятно и сомнительно.

Заранее спасибо.

 

[dreadangel]

hxxp://algolist.manual.ru/

ищи там

 

[tobefree]

Google всем в помощь)

 

[Dimasmir]

dreadangel, спасибо.
tobefree, не спасибо. Сам попробовал поискать, перед тем, как советовать? Не зря я обратил внимание на то, что нужно понятное объяснение, а не что попало.

 

[tobefree]

не знаю как ты искал.
Минуты поиска через гугл.
http://yagni.com/combsort/index.php

 

[Dimasmir]

Компилятор ругается на отсутствие библиотек и на некоторые строки.
Я может и не прав в своём посте... но твой пост тоже не очень корректен.

 

[tobefree]

У Вас какой компилятор? Вышесказанное действительно имеет место для старых компиляторов. Код представленный там, у меня работает полностью, на компиляторе С++ поддерживающий стандарт.
C++Builder.
P.S Там насколько я заметил, лишь одна функции из библиотеки - это swap. Меняет местави значения двух переменных.

 

[Dimasmir]

У меня Visual Studio. Мы на нём программируем...

 

[tobefree]

У меня Visual Studio. Мы на нём программируем...

Попробуйте так. Проверял в C++Builder, работает. По поводу библиотек, да, там в примере есть неточность. Видимо пример делали в Linux.

// quicksort.cpp

#include <algorithm>
#include <assert>
#include <iostream>
#include <math>
#include <stdlib>
#include <time>
#include <conio>

static int random(int ceiling) {
  return static_cast<int>((static_cast<float>(rand()) / RAND_MAX) * ceiling);
}

static void scramble(int a[], int aSize) {
  for (int i = 0; i < aSize; i++)
    std::swap(a[i], a[std::random(aSize)]);
}

static void makeScrambledArray(int a[], int size) {
  for (int i = 0; i < size; i++)
    a[i] = i;
  scramble (a, size);
}

static bool isSorted(int a[], int aSize) {
  for (int i = 0; i < aSize; i++)
    if (a[i] != i)
      return false;
  return true;
}

// BEGIN-ALGORITHM
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;
  for (;;) {
    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)
      break;
  }
}
// END-ALGORITHM

int main() {
  const int trials = 100;
  double totalTime = 0;
  for (int i = 0; i < trials; i++) 
    {
      const int aSize = 10000;
      int a [aSize];
      makeScrambledArray(a, aSize);
      clock_t startTime = clock();
      combsort(a, aSize);
      clock_t endTime = clock();
      double seconds =
        static_cast<double>(endTime - startTime) / CLOCKS_PER_SEC;
      totalTime += seconds;
      assert(isSorted(a, aSize));
    }
  std::cout << totalTime / trials << std::endl;

  getch();
}

 

[Dimasmir]

Чуть поправил, доработал, сдал.
Большое спасибо.