Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.64
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
#1

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

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

Помогите пожалуйста переделать реализацию сортировки так, чтобы она могла работать с любыми типами данных(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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2009, 22:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация алгоритма сортировки для любых типов данных (C++):

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

Реализация алгоритма сортировки вставками - C++
Мне нужно сделать лабу тема вверху... перед этим прочитал тему http://www.cyberforum.ru/cpp-beginners/thread27084.html все равно не...

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

Реализация алгоритма быстрой сортировки quickSort - C++
это алгоритм быстрой сортировки quickSort прошу напишите значение строк файл исходного кода qs.cpp : #include &quot;stdafx.h&quot;...

Try catch реализация для проверки вводимых типов данных в объект - C++
Доброго времени суток, форум! Прошу помощи в реализации проверки потока ввода в класс на правильность типа данных с помощью try catch....

Засечь время сортировки разных типов данных - C++
Всем доброго времени суток, нужно в программе засечь время выполнения сортировки разными способами, в моём случае это выборки и обмен,и для...

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

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

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

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

Я не сторонник того, чтобы выкладывать готовые решения
Согласен, но мэйби в качестве исключения ?)) Мне завтра нужно сдавать, а больше спросить некого..
0
Evg
Эксперт CАвтор FAQ
18253 / 6378 / 438
Регистрация: 30.03.2009
Сообщений: 17,656
Записей в блоге: 28
11.12.2009, 14:57 #13
Цитата Сообщение от Shim Посмотреть сообщение
Evg, в вашем коде рассмотрены функции перестановки int'ов и double'в, а мне нужно для любых типов данных...
Перставлять - побайтный обмен местами от указателей p1 и p2 размером elem_size. Но функцию сравнения придётся писать для КАЖДОГО типа. Тут либо по одной функции для каждого типа, либо шаблон Си++ (что в конечном итоге так же родит по одной функции каждого типа)
1
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);
}
...
0
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;
    
}
0
13.12.2009, 01:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.12.2009, 01:10
Привет! Вот еще темы с ответами:

Требуется реализация простейшего алгоритма сжатия данных (кодирование повторов) - C++
Требуется программная реализация простейшего алгоритма сжатия данных(кодирование повторов). Обрабатываемые данные в виде текста(файла),...

Работа с табличными базами данных. Реализация функции сортировки. - C++
Вот код моей программы. Необходимо реализовать функцию сортировки данных!!! //project.cpp - Lab. #8 #define lname 80 ...

Написать программу для реализации алгоритма сортировки методом пирамиды - C++
Разработать программу для реализации алгоритма сортировки методом пирамиды. Вывести в диалоге столбчатую диаграмму зависимости времени...

Провести исследования быстродействия алгоритма сортировки для различного числа элементов в массиве - C++
Написать программу , в которой реализируется метод сортировки (пузырьковая , блочная или вставкой - не важно). Провести исследования...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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