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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработать шаблон класса для хранения данных (контейнер) - C++
Я не понял как описать шаблон класса для хранения данных (контейнер). Данные должны хранится, например, в виде массива. Шаблон должен...

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

Отсутствует список аргументов для шаблон класса std::vector - C++
Есть функция: LoadFBX(std::vector* pOutVertexVector); на загрузку модели формата FBX в DX. На std::vector выдает ошибку... Что делать?

Разработать шаблон класса для вывода вектора данных в поток - 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 должен всегда быть инициализирован значением расстояния от центра расчётов.
Yandex
Объявления
13.11.2009, 19:43     Шаблон класса для блочной сортировки
Ответ Создать тему
Опции темы

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