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

Сортировка Шелла - C++

Восстановить пароль Регистрация
Другие темы раздела
C++/CLI WinForms Что значит эта строка http://www.cyberforum.ru/cpp-beginners/thread673002.html
this->button1->Click += gcnew System::EventHandler(this, &Form1::button1_Click);только пожалуйста расскажите подробно.Заранее спасибо
C++ Оператор sizeof Используя оператор sizeof определите и выведите на экран количество байт, необходимых для хранения всех известных Вам простых типов данных: http://www.cyberforum.ru/cpp-beginners/thread672985.html
C++ Удаление элементов из списка
Доброго всем времени суток! в универе начали проходить динамические структуры, дошли до списков. Дали задание составить динамический список STUDENT с полями ФИО, группа, день, месяц и год рождения. Нужно написать фунуцию сортирующую список по возрасту (ну это я сам справлюсь как-нибудь) и функцию удаляющую всех студентов из списка по заданной группе, вот как раз с ней то и проблема. ...
C++ программа и функция с переменным числом параметров
Реализовать функцию с переменным числом параметров. Параметрами являются символы, которые определяют, какие функции должны быть выполнены. Функции необходимо вызвать, используя указатели на них. Реализовать функцию с переменным числом параметров. Параметрами являются символы, которые определяют, какие функции должны быть выполнены. Функции необходимо вызвать, используя указатели на них. Помогите...
C++ Повторное применение оператора delete http://www.cyberforum.ru/cpp-beginners/thread672956.html
Это нормально так делать? в одном учебнике нашел: Вы можете попасть в ситуацию, когда delete вызывается неоднократно для одного и того же объекта ............ Чтобы избежать повторного применения delete к указателю, возмите за правило обнулять указатель после уничтожения объекта: Monster* Borg=new Monster; delete Borg; Borg=0; //Теперь повторный вызов delete безопасен
C++ Преобразование изображения в текст в общем необходимо написать программу для преобразования картинки в текст, как это сделать и вообще с чего начать? подробнее

Показать сообщение отдельно
ogcjm
0 / 0 / 0
Регистрация: 22.09.2012
Сообщений: 34
17.10.2012, 19:08     Сортировка Шелла
Скажите пожалуйста какой из вариантов лучше использовать для реализации сортировки Шелла?
Второй вариант меня смущает тем, что там больше функций? Это сильно замедлит работу по сравнению с первым вариантом?

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
39
40
41
42
43
44
45
46
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;
    }
  }
}
Второй вариант:

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
39
40
41
42
43
44
45
46
47
48
//вычисляет коэффициент седжвика с номером s
long calcSegvik(int s){
    if(s % 2) 
        return 8 * pow(2.0, s) - 6 * pow(2.0, (s+1)/2) + 1;
    else
        return 9 * pow(2.0, s) - 9 * pow(2.0, s/2) + 1;
}
 
//вычисляет последовательность длин подсписков
int  increment(long inc[], long size) {
    int i = 0;
 
    do{
        inc[i] = calcSegvik(i);
    }while(3 * inc[i++] < size);
 
    return i - 1;
}
 
//сортировка вставками начиная с индекса start с шагом inc
//сортирует только элементы, которые входят в множество {a | a попадает в start + k * inc}
void insertSort(int list[], int size, int start, int inc){
    int location;
    int newelement;
 
    for(int i = start + inc; i < size; i += inc){
        newelement = list[i];
        location = i - inc;
        
        while(location >= start && list[location] > newelement){
            list[location + inc] = list[location];
            location -= inc;
        }
 
        list[location + inc] = newelement;
            
    }
}
 
//сортировка Шелла
void shellSort(int a[], int size){
  long seq[40];
  
  //в s хранится последний элемент (его индекс) из массива коэф. седжвика seq
  for(int s = increment(seq, size); s >= 0; s--)
    for(int i = 0; i < seq[s]; i++)
        insertSort(a, size, i, seq[s]);
}
Добавлено через 17 часов 18 минут
up up up...

Добавлено через 8 минут
UpUpUp....
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 16:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru