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

Реализация алгоритма сортировки для любых типов данных - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.64
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
08.12.2009, 22:49     Реализация алгоритма сортировки для любых типов данных #1
Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(int, double, etc) Т.е. могла сортировать не только целые числа, но и строки, etc.. Начал делать через функцию обратного вызова и застрял..

вот header:

sort.h
typedef int (*cmp_fnx)(void*, void*)

void sort(void *v, int c, int s, cmp_fnx);
//указатель на массив, количество элементов, на размерность каждого элемента

Сам алгоритм:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Sort1(int c[], int max)
// c[] - наш массив
// max - размер массива c
{
for (int i1 = 0; i1 < max; i1++)
{
for (int i = max-2; i >= i1; i--)
{
if (c[i+1] > c[i]) continue;
 
Change(c, i, i+1); // Двигаем минимальное число вверх, тем самым сортируя числа
}
}
}
Нужно реализовать функцию, которую мы объявляем в хедере, и чтобы она могла работать с любыми типами данных...данных int, double, etc... т.е. была универсальной. Вот как-то так...мэйби кто нибудь подскажет ?)) Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2009, 22:49     Реализация алгоритма сортировки для любых типов данных
Посмотрите здесь:

C++ Работа с табличными базами данных. Реализация функции сортировки.
Реализация алгоритма Рабина-Карпа для двух однонаправленных линейных списков C++
Засечь время сортировки разных типов данных C++
C++ Провести исследования быстродействия алгоритма сортировки для различного числа элементов в массиве
Требуется реализация простейшего алгоритма сжатия данных (кодирование повторов) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
08.12.2009, 22:51     Реализация алгоритма сортировки для любых типов данных #2
Цитата Сообщение от Shim Посмотреть сообщение
чтобы она могла работать с любыми типами данных(int, double, etc)
почитай о шаблонах!)
Андрейка
410 / 214 / 24
Регистрация: 25.03.2009
Сообщений: 716
08.12.2009, 23:01     Реализация алгоритма сортировки для любых типов данных #3
Shim, Вандервуд , Джосаттис шаблоны С++ тебе этого на долго хватит)
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
09.12.2009, 00:16  [ТС]     Реализация алгоритма сортировки для любых типов данных #4
вот как-то так ?)) У меня не очень много времени, поэтому прошу отвечать по существу, если не сложно))

C++
1
2
3
4
template <class T> void sort ( unsigned int n, T * p )
{
...
}
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
09.12.2009, 01:28     Реализация алгоритма сортировки для любых типов данных #5
Shim, да.

T - Это тип твоего массива
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
09.12.2009, 03:08  [ТС]     Реализация алгоритма сортировки для любых типов данных #6
Цитата Сообщение от Monte-Cristo Посмотреть сообщение
Shim, да.

T - Это тип твоего массива
Просто запихнуть алгоритм в фигурные скобки я так думаю будет недостаточно)) А как это должно выглядеть в коде ? Черкани пожалуйста)
Sayrus89
 Аватар для Sayrus89
31 / 31 / 1
Регистрация: 26.10.2009
Сообщений: 98
09.12.2009, 05:07     Реализация алгоритма сортировки для любых типов данных #7
Вот код шаблонной функции для поиска значения в массиве и возврата его индекса (для примера) :
C++
1
2
3
4
5
6
7
8
9
10
template <typename T>
int Find(T& value, T* arr, int size)
{
    for (int i = 0; i < size; i++) {
        if (arr[i] == value) {
            return (i);
        }
    }
    return (-1) //значение не найдено
}
Пример использования:
C++
1
2
3
4
5
intArr[4] = {1, 2, 3, 4};
int res,
    x = 3;
res = Find(x, intArr, 4); // вызов Find<int> по дедукции
res = Find<int>(x, intArr, 4); //явный вызов Find<int>
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
10.12.2009, 21:43  [ТС]     Реализация алгоритма сортировки для любых типов данных #8
через шаблон не годится, нужно делать через функцию обратного вызова...я не врубаюсь..
например для того чтобы поменять местами элементы(n1 и n2):

C++
1
2
3
4
5
6
for( int j=0; j<s; j++)
{
char c = *((char*)v + s*n1)+j);
*((char*)v +s*n1)+j)=*(((char*)v + s*n2)+j);
*(((char*)v + s*n2)+j)=c;
}
не знаем тип данных, идем по байтам.. Что-то такое должно получиться, помогите пожалуйста.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
10.12.2009, 23:21     Реализация алгоритма сортировки для любых типов данных #9
Сделаем обобщённую функцию, которая в массиве произвольного типа переставляет местами два элемента. Для сортировки нужна будет аналогичная функция, которая сравнивает два элемента. Программу не запускал и не проверял - чисто чтобы объяснить, по какому принципу

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
/* data - указатель на массив
 * elem_size - размер елемента массива
 * i1, i2 - индексы элементов, которые надо поменять местами
 * swap_func - указатель на функцию для конкретного типа, которая будет переставлять
 * местами элементы */
void
swap (void *data, int elem_size, int i1, int i2, void (*swap_func)(void*, void*))
{
  void *p1, *p2;
 
  /* Вычисляем адреса элементов массива */
  p1 = (char*)data + i1*elem_size;
  p2 = (char*)data + i2*elem_size;
 
  /* Меняем местами элементы */
  swap_func (p1, p2);
}
 
/* Функция, для обмена местами двух int'ов */
void
swap_int (void *p1, void *p2)
{
  int *pp1, *pp2, tmp;
 
  pp1 = (int*) p1;
  pp2 = (int*) p2;
 
  tmp = *pp1;
  *pp1 = *pp2;
  *pp2 = tmp;
}
 
/* Функция, для обмена местами двух double'ов */
void
swap_double (void *p1, void *p2)
{
  double *pp1, *pp2, tmp;
 
  pp1 = (int*) p1;
  pp2 = (int*) p2;
 
  tmp = *pp1;
  *pp1 = *pp2;
  *pp2 = tmp;
}
 
int
main (void)
{
  int ar1[5] = { 11, 22, 33, 44, 55 };
  double ar2[5] = { 11.11, 22.22, 33.33, 44.44, 55.55 };
 
  /* Меняем местами ar1[2] и ar1[3] */
  swap (ar1, sizeof (ar1[0]), 2, 3, swap_int);
 
  /* Меняем местами ar2[3] и ar2[4] */
  swap (ar2, sizeof (ar2[0]), 3, 4, swap_double);
 
  return 0;
}
Добавлено через 2 минуты
В случае сортировки у тебя должен быть указатель на функцию, которая делает сравнение элементов и возвращает -1, 0 или 1 в зависимости от результата (меньше, равно, больше). Чтобы поменятть местами два элемента, такой мазохизм, как я привёл, не нужен. Можно просто в массиве побайтово поменять два куска от указателей на элементы. Куски размером elem_size байт
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
11.12.2009, 01:05  [ТС]     Реализация алгоритма сортировки для любых типов данных #10
Evg, спасибо, идею я вроде понял, но вот код аццкий)) Вот у меня библиотека состоит из header'а и cpp'шного файла xsort(я в 1м посте их написал), мне надо сделать, чтобы у меня вот в этом cpp'шном файле реализовалась функция которая может сортировать любые данные...а не просто менять 2 элемнта местами.. Я вот примерно функцию сравнения 2 чисел типа int попытался написать, но насколько это правильно не знаю, ибо не умею программировать, а задание сделать надо)) А как сделать для любых типов данных вообще не представляю(((

C++
1
2
3
4
5
6
7
int int_cmp(const void *a, const void *b)
{
    const int *ia = (const int *)a;
    const int *ib = (const int *)b;
 
    return *ia  - *ib;  
}
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
11.12.2009, 11:02     Реализация алгоритма сортировки для любых типов данных #11
Цитата Сообщение от Shim Посмотреть сообщение
Я вот примерно функцию сравнения 2 чисел типа int попытался написать, но насколько это правильно не знаю, ибо не умею программировать, а задание сделать надо))
Не совсем правильно. Если одно число меньше другого, надо вернуть -1, если равны - 0, если больше, то +1. Я не сторонник того, чтобы выкладывать готовые решения. Пример привёл для того, потому что словами это не опишешь.

Цитата Сообщение от Shim Посмотреть сообщение
А как сделать для любых типов данных вообще не представляю(((
В моём примере было обмен местами двух элементов. А для сортировки надо, по сути дела сравнить и поменять
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
11.12.2009, 14:34  [ТС]     Реализация алгоритма сортировки для любых типов данных #12
Evg, в вашем коде рассмотрены функции перестановки int'ов и double'в, а мне нужно для любых типов данных...

Я не сторонник того, чтобы выкладывать готовые решения
Согласен, но мэйби в качестве исключения ?)) Мне завтра нужно сдавать, а больше спросить некого..
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
11.12.2009, 14:57     Реализация алгоритма сортировки для любых типов данных #13
Цитата Сообщение от Shim Посмотреть сообщение
Evg, в вашем коде рассмотрены функции перестановки int'ов и double'в, а мне нужно для любых типов данных...
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
11.12.2009, 15:20  [ТС]     Реализация алгоритма сортировки для любых типов данных #14
Цитата Сообщение от Evg Посмотреть сообщение
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
не, через шаблон не годится, ибо препод сказал что на лекц. нам про шаблоны не читал.

Добавлено через 16 минут
Вот пример: поиск max в массиве (используем тип указателя viod* который может указывать на что угодно). Мне нужно по-аналогии сделать..

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
typedef int(*fxcomp)(void*, void*)
int max (void*, int n, int sz, fxcomp)
{
int max=0
for(int i=1; i<n; i++)
{
void*pi=(char*)v + i*sz;
void*pmax=(char*)v + max*sz;
if (f(pmax, pi)<0)
max=i;
}
return max;
}
 
int comp_double(void*d1, void*d2)
{
return*(double*)d1 - *(double*)d2;
}
#define N 100
void main()
{
double d[N];
...
int m=max(d,N,sizeof(double),comp_double);
double max = v[max];
}
int comp_rect(void*r1, void*r2)
{
double s1 = rects(*(rect*)r1);
double s2 = rects(*(rect*)r2);
return s1-s2;
}
void main()
{
rect rc[N]
int m = max(rc, N, sizeof(rect)), comp_rect);
}
...
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
13.12.2009, 01:10  [ТС]     Реализация алгоритма сортировки для любых типов данных #15
Цитата Сообщение от Evg Посмотреть сообщение
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
не надо для каждого типа по функции делать..вот когда у нас целочисленные(инты) мы можем без проблем поменять элементы местами, вводим 3ю переменную, и сравниваем с ней, а когда мы не знаем тип, делаем так, вот есть 2 элемента, n1 и n2, каждый размером S байт, меняем побайтово, а я не могу это запихнуть в то место, ибо не знаю как написать, где у меня в алгоритме сортировки элементы меняются местами, думаю что вызову функцию из библиотеки, вот в библиотеку мне осталось записать функцию, которая должна сортировать любые типы данных, задание-то заключается в том, чтобы написать универсальную библиотеку. Помогите пожалуйста))

[img]http://i076.***********/0912/b9/43321bc3d6da.jpg[/img]

Добавлено через 18 минут
что-то вот как-то так: (j - сдвиг на сколько-то байт)

C++
1
2
3
4
5
6
7
8
typedef void(*cmp_f)(void*, void*)
{
    for (int j=0; j<s; j++);
    char c=*((char*)a1+j);
    *((char*)a1+j)=*((char*)a2+j);
    *((char*)a2+j=c;
    
}
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
13.12.2009, 17:38     Реализация алгоритма сортировки для любых типов данных #16
Shim, из твоих рассуждений ничерта не понял. Одно могу сказать тебе точно - универсальную функцию нельзя написать ПО ОПРЕДЕЛЕНИЮ, т.к. неизвестно, как СРАВНИВАТЬ два куска памяти (в которых расположена переменная заранее неизвестного типа). Ибо сортировка основывается на сравнении. Универсальность в данном случае заключается в том, что ты заводишь новый тип (или берёшь существующий), пишешь для этого типа функцию сравнения и подаёшь указатель на неё в функцию сортировки. Сама функция сортировки при этом не меняется и сортировка работает для любого типа. А функция сравнения по сути является некоторым параметром сортировки, определяющим тип аргументов. Для самой функции сортировки этот параметр прозрачен, т.к. сортировка просто вызывает эту функцию и передаёт указатель на участки памяти. Что делается в этой функции (т.е. как конкретно идёт сравнение) - функции сортировки безразлично

По поводу твоего кода, я так же не пойму, что ты хочешь. Написать функцию или описать тип указателя на функцию. И почему она у тебя называется cmp (сравнить), в то время как функция занимается обменом двух участков памяти (swap)
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
13.12.2009, 18:25  [ТС]     Реализация алгоритма сортировки для любых типов данных #17
Цитата Сообщение от Evg Посмотреть сообщение
Shim, из твоих рассуждений ничерта не понял. Одно могу сказать тебе точно - универсальную функцию нельзя написать ПО ОПРЕДЕЛЕНИЮ, т.к. неизвестно, как СРАВНИВАТЬ два куска памяти (в которых расположена переменная заранее неизвестного типа). Ибо сортировка основывается на сравнении. Универсальность в данном случае заключается в том, что ты заводишь новый тип (или берёшь существующий), пишешь для этого типа функцию сравнения и подаёшь указатель на неё в функцию сортировки. Сама функция сортировки при этом не меняется и сортировка работает для любого типа. А функция сравнения по сути является некоторым параметром сортировки, определяющим тип аргументов. Для самой функции сортировки этот параметр прозрачен, т.к. сортировка просто вызывает эту функцию и передаёт указатель на участки памяти. Что делается в этой функции (т.е. как конкретно идёт сравнение) - функции сортировки безразлично

По поводу твоего кода, я так же не пойму, что ты хочешь. Написать функцию или описать тип указателя на функцию. И почему она у тебя называется cmp (сравнить), в то время как функция занимается обменом двух участков памяти (swap)
эээм...нужно написать универсальную библиотеку, а не функцию, т.е. чтобы библиотеку потом можно было бы прикрутить куда нибудь, идею я написал как сам понял - когда в сортировке доходит до той части где меняются местами элементы, вызывается из моей библиотеки эта функция, которая вне зависимости от типа данных, меняет нам элементы побайтово(ex: если в одной аудитории 20 студентов и в другой 20, нам надо поменять их местами, мы же не можем взять их в охапку и перетащить...вот по одному и меняем).
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
13.12.2009, 21:02     Реализация алгоритма сортировки для любых типов данных #18
Ещё раз говорю. Проблема не в том, чтобы поменять местами, а в том, чтобы сравнить
Shim
 Аватар для Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
14.12.2009, 01:27  [ТС]     Реализация алгоритма сортировки для любых типов данных #19
тогда хз, я уже начинаю подозревать что задание невыполнимое...(по крайней мере для меня)

Добавлено через 16 минут
сейчас уже ничего не соображаю, буду завтра на свежую голову думать..
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2009, 23:44     Реализация алгоритма сортировки для любых типов данных
Еще ссылки по теме:

Написать программу для реализации алгоритма сортировки методом пирамиды C++
C++ Реализация алгоритма быстрой сортировки quickSort
C++ Реализация алгоритма пузырьковой сортировки

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16827 / 5248 / 321
Регистрация: 30.03.2009
Сообщений: 14,132
Записей в блоге: 26
20.12.2009, 23:44     Реализация алгоритма сортировки для любых типов данных #20
Shim, я уже и позабыл, что было в первом посте...

Давай начнём со следующего. Для начала просто напиши сортировку int'ов без всяких дополнительных премудростей. То, что у тебя написано, в принципе верно (по крайней мере с ходу кажется, что верно), но несколько "некрасиво". Реализуй метод "сортировка пузырьком". В инете навалом мест, где это описано. Почему прошу сделать аккуратно? Потому что когда будем делать навороты над этой программой, то при аккуратной (классической) записи проще будет воспринимать и проще не наделать косяков. Хотя если ты готов работать со своей версией, то можно работать и на ней.

Если готов рабоатть с текущей версией, то напиши полную программу, включая main и Change (правда по английски это называется не "change", а "swap") и добейся её работоспособности. Для порядку лучше иметь несколько массивов (хотя бы два). После чего поедем дальше
Yandex
Объявления
20.12.2009, 23:44     Реализация алгоритма сортировки для любых типов данных
Ответ Создать тему
Опции темы

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