Форум программистов, компьютерный форум CyberForum.ru

Сортировка методом шелла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.86
grrrrr
 Аватар для grrrrr
45 / 45 / 7
Регистрация: 21.04.2009
Сообщений: 265
17.06.2009, 17:04     Сортировка методом шелла #1
День добрый! Хочу разобраться с алгоритмом. Перепишете его пожалуйста без шаблонов, если я правильно понял что это такое. Спасибо.

Вот алгоритм:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int increment(long inc[], long 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;
  } while(3*inc[s] < size);  
 
  return s > 0 ? --s : 0;
}
 
template<class T>
void shellSort(T a[], long size) {
  long inc, i, j, seq[40];
  int s;
 
  // вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
    // сортировка вставками с инкрементами inc[] 
    inc = seq[s--];
 
    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];
      a[j+inc] = temp;
    }
  }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2009, 17:04     Сортировка методом шелла
Посмотрите здесь:

Сортировка методом Шелла C++
C++ Сортировка методом Шелла
Сортировка строк матрицы методом Шелла C++
C++ Сортировка динамических структур методом шелла
Сортировка методом Шелла, ошибки чуть ли не в каждой строке C++
C++ Сортировка массива методом Шелла
C++ Сортировка методом Шелла
Сортировка двумерного массива Методом Шелла (по убыванию) C++
Сортировка методом Шелла C++
Сортировка методом Шелла C++
Сортировка методом Шелла и другое на С++ C++
C++ Сортировка массива методом Шелла пожалуйста

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2295 / 1665 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
17.06.2009, 17:32     Сортировка методом шелла #2
1. Убираем template<class T>.
2. Заменяем T на нужный нам тип, например int.
Получаем сортировку Шелла целочисленного массива.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int increment(long inc[], long 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;
  } while(3*inc[s] < size);  
 
  return s > 0 ? --s : 0;
}
 
void shellSort(int a[], long size) {
  long inc, i, j, seq[40];
  int s;
 
  // вычисление последовательности приращений
  s = increment(seq, size);
  while (s >= 0) {
        // сортировка вставками с инкрементами inc[] 
        inc = seq[s--];
 
    for (i = inc; i < size; i++) {
      int temp = a[i];
      for (j = i-inc; (j >= 0) && (a[j] > temp); j -= inc)
        a[j+inc] = a[j];
      a[j+inc] = temp;
    }
  }
}
Yandex
Объявления
17.06.2009, 17:32     Сортировка методом шелла
Ответ Создать тему
Опции темы

Текущее время: 14:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru