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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
dware
0 / 0 / 0
Регистрация: 20.10.2009
Сообщений: 11
#1

Шаблон класса для блочной сортировки - C++

09.11.2009, 20:13. Просмотров 1094. Ответов 4
Метки нет (Все метки)

Есть задание реализовать шаблон класса, содержащий разные методы сортировок. Тип сортируемых элементов передаётся как параметр. В общем-то, всё получается, кроме блочной сортровки (http://ru.wikipedia.org/wiki/Блочная_сортировка). Насколько я понял, для неё вообще не получится реализовать шаблон по причине того, что "Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой."
Если я неправильно думаю, помогайте, пожалуйста
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2009, 20:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Шаблон класса для блочной сортировки (C++):

Реализация блочной сортировки файла - C++
Здравствуйте! Есть задача,как следствие ее нужно решить)) Я прекрасно знаю и понимаю,что никто за меня решать здесь не собирается.Но...

Шаблоны функций, Ошибка: для использования класса шаблон требуется список аргументов шаблон - C++
Есть у меня 3 структуры Трамвай , Троллейбус , Автобус. Для автобуса определены функции (работают) Троллейбус и Трамвай одинаковые поля...

Написать шаблон функции для сортировки массивов действительных и целых чисел - C++
Заданы элементы массива. Написать шаблон функции для сортировки массивов действительных и целых чисел. Поможете?:scratch:

Шаблон класса для работы с массивом - C++
помогите пожалуйста! Нужно создать шаблон класса для работы с одномерным массивом. Выполнить тестирование путем создания и обработки...

Шаблон для класса с перегрузками операторов - C++
Доброе время суток. Есть класс Fract реализующий дробь. Не получается сделать шаблон, чтобы можно было складывать Fract<int> + Fract<long>...

Шаблон класса для работы с одномерным массивом - C++
Создать шаблон класса для работы с одномерным массивом. Выполнить тестирование путем создания и обработки массивов, со- ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
TurboDune
22 / 22 / 1
Регистрация: 20.02.2009
Сообщений: 59
09.11.2009, 22:27 #2
Допустим нет ничего невозможно .

Хоть бы привёл для интереса сигнатуру шаблона, было бы проще думать как что-нибудь встроить.
Я бы такую задачу решал следующим образом:
Вторым параметром шаблона ввёл класс, который сможет определить размер корзины или нормальным языком - максимальное расстояние между соседними элементами.
Тогда изначально кол-во корзин - 0. Вставляем первый элемент - заводим первую корзину, как начало отсчёта. Вставляем второй и последующие элементы - рассчитываем расстояние относительно первого и заводим (если надо) новую корзину, или используем существующую (созданную ранее). Тогда после всех вставок получим какой-то набор корзин. Причём если попробовать этот набор организовать на основании списка, то по памяти будет очень хорошо. Ну а дальше действия как описаны на приводимом сайте.

Например (пишу без проверок, но идея должна быть ясна):
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
template<class T>
struct Basket
{
    std::list<T> m_listElements;
    long m_lDistance;
    Basket(long lDistance)
       : m_lDistance(lDistance)
    {  }
};
template<class T, class LengthTraits = LengthTraitsTmpl<T> >
struct A
{
    T m_vFirst; // Начало отсчёта
    std::list<Basket> listBaskets; /* список корзин. списков можно завести 2 - в зависимости от знака
                                                смещения от начала отсчёта. А можно просто при каждой вставке 
                                                (если нужно) перемещать начало отсчёта таким образом, 
                                                чтобы все смещения были положительные */
   void insert(const T& v)
   {
       long lDistance = LengthTraits::GetDistance(m_vFirst, v);
       for(std::list<Basket>::iterator it = listBaskets.begin(); it != listBaskets.end(); ++it)
       {
            if(it->m_lDistance == lDistance)
            {
                it->m_listElements.push_back(v);
                break;
            }
            if(it->m_lDistance > lDistance)
            {
                // Заводим новую корзину
                Basket basket(lDistance);
                basket.push_back(v);
                listBaskets.insert_before(it, basket);
                break;
            }
       }
   }
};
 
template<class T>
struct LengthTraitsTmpl
{
     long GetDistance(const T& f, const T& v);
};
 
// Теперь пишем специализации для необходимых типов:
 
// для целого
template<>
struct LengthTraitsTmpl<int>
{
     static long GetDistance(const int& f, const int& v)
     {
          return (v - f) / 10; // Например по 10 элементов в корзине
     }
};
 
// для строки
template<>
struct LengthTraitsTmpl<std::string>
{
     static long GetDistance(const std::string& f, const std::string& v)
     {
          // строки можно попробовать распихать по корзинам в виде алфавита
          // это только пример, потому что здесь необходимо вывести формулу
          // для номера корзины в зависимости от индекса символа в строке.
          return v[0] - f[0];
     }
};
 ну и так далее...
dware
0 / 0 / 0
Регистрация: 20.10.2009
Сообщений: 11
10.11.2009, 22:33  [ТС] #3
Идею вроде понял, нужно более детально разобраться. Спасибо большое за помощь!
dware
0 / 0 / 0
Регистрация: 20.10.2009
Сообщений: 11
13.11.2009, 19:28  [ТС] #4
а что вот это означает:
C
1
2
 Basket(long lDistance)
       : m_lDistance(lDistance)
?
TurboDune
22 / 22 / 1
Регистрация: 20.02.2009
Сообщений: 59
13.11.2009, 19:43 #5
Цитата Сообщение от dware Посмотреть сообщение
а что вот это означает:
C
1
2
 Basket(long lDistance)
       : m_lDistance(lDistance)
?
Конструктор класс Basket, при вызове конструктора член класса m_lDistance будет инициализирован переданным значением.
Сделано изходя из предположения, что объект класса Basket должен всегда быть инициализирован значением расстояния от центра расчётов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2009, 19:43
Привет! Вот еще темы с ответами:

Шаблон класса для работы с комплексными числами - C++
Есть такая программа: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; template&lt; class T &gt; class Complex; ...

Реализовать шаблон класса для хранения динамического списка - C++
Нужно реализовать: 1.Операции вставки элемента в начало списка 2.Операцию удаления первого элемента 3.Деструктор высвобождающий всю...

Разработать шаблон класса для реализации односвязного списка - C++
Помогите пожалуйста разработать шаблон класса для реализации односвязного списка.

Шаблон класса Node для узла связного списка - C++
Здравствуйте, помогите пожалуйста реализовать и протестируйте функцию: template &lt;class T&gt; Node&lt;T&gt; *GetNode(const T &amp;item, Node&lt;T&gt;...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.11.2009, 19:43
Ответ Создать тему
Опции темы

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