VPF::Проблема с сортировкой Шелла - Форум программистов

Bugrimov

Дата 15.12.2012, 14:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 8.11.2012

Репутация: нет
Всего: нет

Доброе время суток!
Сейчас занимаюсь методами сортировки. Столкнулся с проблемой.

Код


int SortShell(int *AftSort, int SIZE)
{
    int i, j, k, r;
    int temp;
    int M = 0, C = 0;
    
    int m = (int)ceil((log(SIZE)/log(2))-1);

    int *h = (int*)malloc(sizeof(int) * m); // выделяю память под динамический массив
    
    system("cls");
    for (r = 0; r < m; r++) {
        if (!r) h[r] = 1;
        else h[r] = h[r-1] * 2 + 1; 
    }
    for(k = m; k >= 0; k--) 
    {        
        for(i = h[k]-1; i < SIZE; i++) 
        {
            temp = AftSort[i];
            M++;

            j = i - k;
            C++;
            
            while((j >= 0) && (temp < AftSort[j])) 
            {
                AftSort[j + k] = AftSort[j];
                j = j - k;
                M++;
                C++;
            }
            AftSort[j + k] = temp;
            M++;
        }    }
    comp = C;
        tran = M;
    free(h);
    printf("\n МЕТОД ШЕЛЛА\n\n");
    return 0;
}

Программа аварийно закрывается при вызове функции. Кто работал с сортировками, подскажите пожалуйста где я мог допустить ошибку?

NoviceF

Дата 15.12.2012, 18:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 13.3.2012
Где: Ростов-на-Дону

Репутация: 2
Всего: 2

Ну учитывая, что написано на Си, скорее всего - выход за границы массива. Откуда взят алгоритм? Либо ошибка в алгоритме, либо допущена ошибка, при переписывании. Прогон на дебаге поспособствует поиску места, где вылетает smile

Добавлено через 3 минуты и 16 секунд
Не проверял, но викки вряд ли станет обманывать, тут должно всё работать, перепишите свою функцию по аналогии

http://ru.wikibooks.org/wiki/%D0%9F%D1%80%...B%D0%B0#C.2B.2B

Код


int increment(long inc[], long size) {
// inc[] массив, в которые заносятся инкременты
// size размерность этого массива
 int p1, p2, p3, s;
 
  p1 = p2 = p3 = 1;
  s = -1;
  do {// заполняем массив элементов по формуле Роберта Седжвика
    if (++s % 2) {
      inc[s] = 8*p1 - 6*p2 + 1;
    } else {
      inc[s] = 9*p1 - 9*p3 + 1;
      p2 *= 2;
      p3 *= 2;
    }
        p1 *= 2;
// заполняем массив, пока текущая инкремента хотя бы в 3 раза меньше количества элементов в массиве
  } while(3*inc[s] < size);  
 
  return s > 0 ? --s : 0;// возвращаем количество элементов в массиве
}
 
template<class T>
void shellSort(T a[], long size) {
// inc инкремент, расстояние между элементами сравнения
// i и j стандартные переменные цикла
// seq[40] массив, в котором хранятся инкременты
  long inc, i, j, seq[40];
  int s;//количество элементов в массиве seq[40]
 
  // вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
        //извлекаем из массива очередную инкременту
        inc = seq[s--];
// сортировка вставками с инкрементами inc
    for (i = inc; i < size; i++) {
      T temp = a[i];
// сдвигаем элементы до тех пор, пока не дойдем до конца или не упорядочим в нужном порядке
      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
        a[j+inc] = a[j];
// после всех сдвигов ставим на место j+inc элемент, который находился на i месте
      a[j+inc] = temp;
    }
  }
}

Добавлено через 7 минут и 11 секунд
Вообще есть хорошая книжка, рекомендую: Роберт Седжвик "Фундаментальные алгоритмы на с++".

Bugrimov

Дата 15.12.2012, 19:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 8.11.2012

Репутация: нет
Всего: нет

Видел я этот код, хотелось бы что отличное от него написать. Я по этому и обратился за советом. Я отдельно проверял, что выводят переменные. Я грешу на массив h. Никак не пойму почему не работает.

Albor

Дата 15.12.2012, 21:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

18-я строка кода

Код


for(i = h[k]-1; i < SIZE; i++)

Не должно быть h[k-1]?

Bugrimov

Дата 16.12.2012, 09:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 24
Регистрация: 8.11.2012

Репутация: нет
Всего: нет

Цитата(Albor @ 15.12.2012, 21:42

)

h[k-1]

Я так понимаю должно быть так?

Добавлено через 35 секунд
Или нет?

Добавлено через 6 минут и 52 секунды
Как должно быть???

Albor

Дата 17.12.2012, 09:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 589
Регистрация: 28.2.2009

Репутация: 2
Всего: 9

Цитата(Bugrimov @ 16.12.2012, 08:06

)

Я так понимаю должно быть так?

Добавлено через 35 секунд
Или нет?

Добавлено через 6 минут и 52 секунды
Как должно быть???

Вы выделяете память под массив из m элементов:

Код


  int m = (int)ceil((log(SIZE)/log(2))-1);
    int *h = (int*)malloc(sizeof(int) * m); // выделяю память под динамический массив

Потом используете так

Код


  for(k = m; k >= 0; k--) 
    {        
        for(i = h[k]-1; i < SIZE; i++) 
//.......

k=m - k индексирует элемент за пределами массива, поскольку индексация начинается с нуля, и поэтому h[k] пытается получить значение из-за пределов массива. Иногда такое срабатывает, тогда ошибку искать тяжелее. В суть вашего кода не вникал, потому и задал наводящий вопрос. Вообще-то, в режиме отладки вы и сами бы нашли причину, а так, врядли кому интересно дебажить ваш код.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »