Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.54/63: Рейтинг темы: голосов - 63, средняя оценка - 4.54
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
1

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

08.12.2009, 22:49. Показов 12580. Ответов 38
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(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... т.е. была универсальной. Вот как-то так...мэйби кто нибудь подскажет ?)) Заранее спасибо.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.12.2009, 22:49
Ответы с готовыми решениями:

Реализовать три любых алгоритма сортировки матрицы на выбор
Всем привет форумчане, сижу и ломаю голову над заданной задачей. А точнее как ее реализовать т.к в...

Реализация алгоритма сортировки Шелла
Здравствуйте! Помогите пожалуйста с реализацией алгоритма сортировки Шелла. Вот дан простой...

Реализация алгоритма сортировки массива
Добрый день !!! Помогите пожалуйста с реализацией алгоритма сортировки массива. Нашел код, но не...

Реализация алгоритма сортировки слиянием
Имеется массив строк вида char lent где каждая строка уже отсортирована по возрастанию. Нужно...

38
2816 / 1407 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
08.12.2009, 22:51 2
Цитата Сообщение от Shim Посмотреть сообщение
чтобы она могла работать с любыми типами данных(int, double, etc)
почитай о шаблонах!)
1
425 / 229 / 87
Регистрация: 25.03.2009
Сообщений: 744
08.12.2009, 23:01 3
Shim, Вандервуд , Джосаттис шаблоны С++ тебе этого на долго хватит)
1
25 / 25 / 0
Регистрация: 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 )
{
...
}
0
2816 / 1407 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
09.12.2009, 01:28 5
Shim, да.

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

T - Это тип твоего массива
Просто запихнуть алгоритм в фигурные скобки я так думаю будет недостаточно)) А как это должно выглядеть в коде ? Черкани пожалуйста)
0
32 / 32 / 7
Регистрация: 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>
1
25 / 25 / 0
Регистрация: 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;
}
не знаем тип данных, идем по байтам.. Что-то такое должно получиться, помогите пожалуйста.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
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 байт
1
25 / 25 / 0
Регистрация: 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;  
}
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
11.12.2009, 11:02 11
Цитата Сообщение от Shim Посмотреть сообщение
Я вот примерно функцию сравнения 2 чисел типа int попытался написать, но насколько это правильно не знаю, ибо не умею программировать, а задание сделать надо))
Не совсем правильно. Если одно число меньше другого, надо вернуть -1, если равны - 0, если больше, то +1. Я не сторонник того, чтобы выкладывать готовые решения. Пример привёл для того, потому что словами это не опишешь.

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

Я не сторонник того, чтобы выкладывать готовые решения
Согласен, но мэйби в качестве исключения ?)) Мне завтра нужно сдавать, а больше спросить некого..
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
11.12.2009, 14:57 13
Цитата Сообщение от Shim Посмотреть сообщение
Evg, в вашем коде рассмотрены функции перестановки int'ов и double'в, а мне нужно для любых типов данных...
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
1
25 / 25 / 0
Регистрация: 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);
}
...
0
25 / 25 / 0
Регистрация: 21.11.2009
Сообщений: 159
13.12.2009, 01:10  [ТС] 15
Цитата Сообщение от Evg Посмотреть сообщение
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
не надо для каждого типа по функции делать..вот когда у нас целочисленные(инты) мы можем без проблем поменять элементы местами, вводим 3ю переменную, и сравниваем с ней, а когда мы не знаем тип, делаем так, вот есть 2 элемента, n1 и n2, каждый размером S байт, меняем побайтово, а я не могу это запихнуть в то место, ибо не знаю как написать, где у меня в алгоритме сортировки элементы меняются местами, думаю что вызову функцию из библиотеки, вот в библиотеку мне осталось записать функцию, которая должна сортировать любые типы данных, задание-то заключается в том, чтобы написать универсальную библиотеку. Помогите пожалуйста))



Добавлено через 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;
    
}
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
13.12.2009, 17:38 16
Shim, из твоих рассуждений ничерта не понял. Одно могу сказать тебе точно - универсальную функцию нельзя написать ПО ОПРЕДЕЛЕНИЮ, т.к. неизвестно, как СРАВНИВАТЬ два куска памяти (в которых расположена переменная заранее неизвестного типа). Ибо сортировка основывается на сравнении. Универсальность в данном случае заключается в том, что ты заводишь новый тип (или берёшь существующий), пишешь для этого типа функцию сравнения и подаёшь указатель на неё в функцию сортировки. Сама функция сортировки при этом не меняется и сортировка работает для любого типа. А функция сравнения по сути является некоторым параметром сортировки, определяющим тип аргументов. Для самой функции сортировки этот параметр прозрачен, т.к. сортировка просто вызывает эту функцию и передаёт указатель на участки памяти. Что делается в этой функции (т.е. как конкретно идёт сравнение) - функции сортировки безразлично

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

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

Добавлено через 16 минут
сейчас уже ничего не соображаю, буду завтра на свежую голову думать..
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
20.12.2009, 23:44 20
Shim, я уже и позабыл, что было в первом посте...

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

Если готов рабоатть с текущей версией, то напиши полную программу, включая main и Change (правда по английски это называется не "change", а "swap") и добейся её работоспособности. Для порядку лучше иметь несколько массивов (хотя бы два). После чего поедем дальше
1
20.12.2009, 23:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2009, 23:44
Помогаю со студенческими работами здесь

Реализация алгоритма сортировки пирамидой
Все привет! Нужна помощь в реализации алгоритма пирамидальной сортировки используя ДВУСВЯЗНУЮ...

Реализация алгоритма сортировки слиянием
помогите, пожалуйста, с реализацией алгоритма сортировки слиянием на VBA.

Реализация алгоритма сортировки вставками
Мне нужно сделать лабу тема вверху... перед этим прочитал тему ...

Реализация алгоритма пузырьковой сортировки
Задача на массивы, где нужно банки переливать (ну, у меня она с этим ассоциируется). Раньше решал...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru