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

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

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

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

08.12.2009, 22:49. Просмотров 3284. Ответов 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++
Всем доброго времени суток, нужно в программе засечь время выполнения сортировки разными способами, в моём случае это выборки и обмен,и для...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
13.12.2009, 17:38 #16
Shim, из твоих рассуждений ничерта не понял. Одно могу сказать тебе точно - универсальную функцию нельзя написать ПО ОПРЕДЕЛЕНИЮ, т.к. неизвестно, как СРАВНИВАТЬ два куска памяти (в которых расположена переменная заранее неизвестного типа). Ибо сортировка основывается на сравнении. Универсальность в данном случае заключается в том, что ты заводишь новый тип (или берёшь существующий), пишешь для этого типа функцию сравнения и подаёшь указатель на неё в функцию сортировки. Сама функция сортировки при этом не меняется и сортировка работает для любого типа. А функция сравнения по сути является некоторым параметром сортировки, определяющим тип аргументов. Для самой функции сортировки этот параметр прозрачен, т.к. сортировка просто вызывает эту функцию и передаёт указатель на участки памяти. Что делается в этой функции (т.е. как конкретно идёт сравнение) - функции сортировки безразлично

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

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

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

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

Если готов рабоатть с текущей версией, то напиши полную программу, включая main и Change (правда по английски это называется не "change", а "swap") и добейся её работоспособности. Для порядку лучше иметь несколько массивов (хотя бы два). После чего поедем дальше
1
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
21.12.2009, 17:37  [ТС] #21
зачем генерировать 2 массива ? мне не нужно демонстрировать как сортируются любые типы данных, эта функция должна быть в библиотеке(какбэ задание-то в этом и заключается), а так программа генерит массив, сортирует его, сравнивает время сортировки с quicksort, и выводит на экран, потом спрашивает - ввести ли отсортированный массив ? y/n - выводит/не выводит -> выход из программы, по этой претензий ко мне не было.
0
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
21.12.2009, 18:03 #22
Цитата Сообщение от Shim Посмотреть сообщение
зачем генерировать 2 массива ?
Можешь вводить массив с клавиатуры, если не впадлу. По мне проще иметь в программе несколько массивов, запустить программу и по печати сразу глазами видеть, правильно работает программа, или нет. Если тебе больше нравится каждый раз вводить массив с клавиатуры - ради бога.

Я пытаюсь тебе по шагам объяснить, как правильно написать программу (чтобы ты сам понял)
0
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
21.12.2009, 21:53  [ТС] #23
Цитата Сообщение от Evg Посмотреть сообщение
Можешь вводить массив с клавиатуры, если не впадлу. По мне проще иметь в программе несколько массивов, запустить программу и по печати сразу глазами видеть, правильно работает программа, или нет. Если тебе больше нравится каждый раз вводить массив с клавиатуры - ради бога.

Я пытаюсь тебе по шагам объяснить, как правильно написать программу (чтобы ты сам понял)
вообще-то у меня массив генерируется рандомно, например 2000 элементов, но для наглядности можно меньше сделать.
0
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
21.12.2009, 22:48 #24
Короче. Напиши рабочий вариант программы и выложи его ЦЕЛИКОМ на форум. Чтобы я хотя бы видел, что ты там уже наваял и как двигаться дальше.
0
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
22.12.2009, 19:03  [ТС] #25
mergesort.h
C++
1
2
3
4
5
6
typedef int (*cmp_fnx)(void*, void*);
 
void mergesort(void *v, int c, int s, cmp_fnx); //указатель на массив, 
                                                              //количество элементов в массиве,
                                                              //размер каждого элемента в байтах, 
                                                             //указатель на функцию

mergesort.сpp

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
#include "mergesort.h"
inline void Change(int a[], int first, int second)
// меняем местами элементы буфера first на second
// a[] - наш массив
// first и second - номера элементов массива a, которые надо поменять местами!
{
    if (first == second) // Если одинаковые номера элементов, то не нужно менять их местами
        return;
    int i;
 
    i = a[second];
    a[second] = a[first];
    a[first] = i;
 
/*
// Можно еще так вот, но так медленнее:
    a[first] += a[second]; // Здесь,
    a[second] = a[first] - a[second]; // здесь,
    a[first] = a[first] - a[second]; // и здесь мы меняем местами два числа в буфере
*/
}
void mergesort(void *v, int c, int s, cmp_fnx cmp);
{
//вот тут планируется реализовать ф-ю для сорт. любых данных
}
main.cpp
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <time.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include "mergesort.h"
 
inline void Change(int a[], int first, int second)
// меняем местами элементы буфера first на second
// a[] - наш массив
// first и second - номера элементов массива a, которые надо поменять местами!
{
    if (first == second) // Если одинаковые номера элементов, то не нужно менять их местами
        return;
    int i;
 
    i = a[second];
    a[second] = a[first];
    a[first] = i;
 
/*
// Можно еще так вот, но так медленнее:
    a[first] += a[second]; // Здесь,
    a[second] = a[first] - a[second]; // здесь,
    a[first] = a[first] - a[second]; // и здесь мы меняем местами два числа в буфере
*/
}
 
int FindMax(int a[], int max)
// Поиск максимального числа в массиве от a[0] до a[max]
// a[] - наш массив
// max - размер массива a
{
    int imax = 0;
 
    for (int i = 0; i <= max; i++)
    {
        if (a[imax] < a[i])
            imax = i;
    }
 
    return imax;
}
 
void Sort(int b[], int max)
// Сортировка номер один!
// b[] - наш массив
// max - размер массива b
{
    int i1;
    for (int i = max - 1; i > 0; i--)
    {
        i1 = FindMax(b, i); // Находим самое максимальное число в промежутке от a[0] до a[i]
 
        Change(b, i, i1); // ставим максимальное число в конец (а именно на место элемента под номером i)
    }
}
 
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); // Двигаем минимальное число вверх, тем самым сортируя числа
        
        }
    }
}
 
void main()
{
    #define MAX 3000
    int a[MAX], b[MAX], c[MAX]; // Объявляем пару буферов
 
/*
// Если записать строки выше, тогда у юзера будет запрашиваться 
// число элементов в массиве
 
    int MAX;
    printf("Enter the size of array with the numbers: ");
    scanf("%i", &MAX);
 
    int *a = new int[MAX]; // Объявляем буфер
    int *b = new int[MAX]; // Объявляем буфер
    int *c = new int[MAX]; // Объявляем буфер
*/
 
    srand((unsigned)time(0));
    int i;
    for (int i = 0; i < MAX; i++)
    {
        a[i] = rand(); // заполняем случайными числами
        b[i] = a[i]; // делаем копию
        c[i] = a[i]; // делаем копию
    }
 
    clock_t begin, end;
    begin = clock();
    Sort(b, MAX); // 
    end = clock();
 
    float f = (float)(end-begin); // Измеряем время, занятое сортировкой
 
    printf ("Sorting %i elements with the sort1 takes     %.0f msec.\r\n\r\n", MAX, f);
 
    begin = clock();
    Sort1(c, MAX); // 
    end = clock();
    float f1 = (float)(end-begin); // Измеряем время, занятое сортировкой
 
 
    printf ("Sorting %i elements with the sort2 takes  %.0f msec.\r\n", MAX, f1);
 
    // Вы хотите просмотреть отсортированные данные?
    printf("\r\n\r\n\r\nDo you want to view the sorting result? (y/n)"); 
    short Key = 0;
 
    while (Key = _getch()) // Ожидание нажатия на кнопку
    {
        if (Key == 'n' || Key == 'N' || Key == 'N') // если нажата кнопк N или Esc, то
            return; // выход
        else if (Key == 'y' || Key == 'Y') // если y, то
            break; // то продолжаем
    }
 
    printf("\r\n\r\n\r\n");
    printf(" N.    unsorted        N.     q sort       N.    merge sort\r\n");
    printf("\r\n");
    for (i = 0; i < MAX; i++)
        printf("%3i.    %5i        %3i.    %5i        %3i.    %5i\r\n", 
        i+1, a[i], i+1, b[i], i+1, c[i]); // Печать содержимого массивов
    printf("\r\nPress any key to continue\r\n");
 
    Key = 0;
 
    while (!Key) Key = _getch(); // Ожидание нажатия на кнопку
}
0
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
22.12.2009, 19:31 #26
Запустил программу, она мне в ответ пишет
Sorting 3000 elements with the sort1 takes 10000 msec.
Ты можешь по этой надписи оценить правильность работы? Я - нет

Я выкинул к чёртовой матери весь твой main и написал свой. Без красоты в виде времени сортировки, случайно сгенерённых массивов, вопросов и прочего. Ты можешь проверять на своём, но я предпочитаю на своём

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    const int MAX = 10;
    int a[MAX] = { 1, 7, 8, 34, 2, 5, 0, 6, 9, 3 };
    int i;
 
    Sort (a, MAX);
    for (int i = 0; i < MAX; i++)
      printf ("%d ", a[i]);
    printf ("\n");
 
    return 0;
}
Результат такой:

Код
0 1 2 3 5 6 7 8 9 34
Т.е. оно по крайне мере работает

--------------------------------------------------------

Шаг N2:
Поменяй функцию Change. Сечай ты передаёшь указатель на начало массива и индексы. Перепиши так, чтобы подавались просто указатели на два элемента массива (т.е. чтобы обмен местами работал обсьрагированно от массива и был универсальным с точностью до типа переменной)

Шаг N3:
Сравнение двух элементов вместо операции "<" или ">" делай через функцию сравнения, которую пока просто напиши рядом и пусть она принимает указатели на два int'а
0
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
22.12.2009, 20:01  [ТС] #27
Цитата Сообщение от Evg Посмотреть сообщение
Запустил программу, она мне в ответ пишет
Sorting 3000 elements with the sort1 takes 10000 msec.
Ты можешь по этой надписи оценить правильность работы? Я - нет

Я выкинул к чёртовой матери весь твой main и написал свой. Без красоты в виде времени сортировки, случайно сгенерённых массивов, вопросов и прочего. Ты можешь проверять на своём, но я предпочитаю на своём

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    const int MAX = 10;
    int a[MAX] = { 1, 7, 8, 34, 2, 5, 0, 6, 9, 3 };
    int i;
 
    Sort (a, MAX);
    for (int i = 0; i < MAX; i++)
      printf ("%d ", a[i]);
    printf ("\n");
 
    return 0;
}
Результат такой:

Код
0 1 2 3 5 6 7 8 9 34
Т.е. оно по крайне мере работает

--------------------------------------------------------

Шаг N2:
Поменяй функцию Change. Сечай ты передаёшь указатель на начало массива и индексы. Перепиши так, чтобы подавались просто указатели на два элемента массива (т.е. чтобы обмен местами работал обсьрагированно от массива и был универсальным с точностью до типа переменной)

Шаг N3:
Сравнение двух элементов вместо операции "<" или ">" делай через функцию сравнения, которую пока просто напиши рядом и пусть она принимает указатели на два int'а
выкинь mergesort.сpp нафиг, он недоделан, поэтому такую ерунду выдает. Твой код у меня тож ошибку выдает - Ошибка error C3861: Sort: идентификатор не найден
0
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
22.12.2009, 20:08 #28
> выкинь mergesort.сpp нафиг, он недоделан, поэтому такую ерунду выдает.

main у тебя в файле main.cpp. И как связано "выкинь mergesort" с тем, что я писал выше - непонятно. Какие ты мне дал исходники, те я и компилял
0
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
22.12.2009, 20:12  [ТС] #29
Цитата Сообщение от Evg Посмотреть сообщение
> выкинь mergesort.сpp нафиг, он недоделан, поэтому такую ерунду выдает.

main у тебя в файле main.cpp. И как связано "выкинь mergesort" с тем, что я писал выше - непонятно. Какие ты мне дал исходники, те я и компилял
в MS Visual Studio C++ компилил ?
0
Evg
Эксперт CАвтор FAQ
17811 / 6017 / 388
Регистрация: 30.03.2009
Сообщений: 16,532
Записей в блоге: 26
22.12.2009, 21:56 #30
Компилил gcc'ями, правда не пойму, какая от этого разница?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.12.2009, 21:56
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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