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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ строки:ПЕРЕВОД ИЗ ОДНОЙ C/ С В ДР http://www.cyberforum.ru/cpp-beginners/thread72072.html
Вывести все числа не превышающие данное N, которые в 2-ной системе счислания имеют симметричную запись ( начинается с 1!). Помогите юному гению в юбке сдать задачу на зачет! Пасибки за понимание
C++ Сортировка пузырьком... Доброе утро/день/вечер!=) У меня есть пару вопросов, на которые я никак не могу найти ответов... Есть программа, в которй проставляется оценка каждого студента за определённый предмет, всё ничего кроме одного, не работает сортировка(по студентам и оценкам) пузырьком... Никаких изменений эта сортировка не принесла...Почитал ваш форум, и натыкался впринцепе на тоже самое, что я в своём коде... http://www.cyberforum.ru/cpp-beginners/thread72069.html
C++ Замена в одномерном массиве, работа со строками из нулей и единиц
HELP!!!я ноль в с++ не могу сделать данные задачи: "Даны одномерные массивы чисел Х,размерностью n и Y,размерностью m. необходимо написать программу с использованием функций в которой будут заменятся нулями все положительные элементы в массивах." "дана строка состоящая из групп нулей и едениц. каждая группа отделяется друг от друга одним или несколькими пробелами. нужно создать программу...
C++ Структуру
Помогите решить задачи...пробовал ничего не смог понять. 1) Определить структуры, описывающие шар и точку в трёхмерном пространстве. Составить и протестировать функцию, которая проверяет, находится ли точка внутри заданного шара. и вторая, уже была но я не смог понять, объяснить 2) Описать процедуру IncTime(H, M, S, T), которая увеличивает на Т секунд время, заданное в часах Н, минутах М...
C++ Алгоритм бинарных вставок http://www.cyberforum.ru/cpp-beginners/thread72058.html
подскажите пожалуйста как изменить алгоритм простых вставок.чтобы преобразовать его в алгоритм бинарных вставок..
C++ Вычислить произведение элементов массива S, значение которых не больше заданного негативного числа Здесь задали на Борланде С++ ну просто нечто (я нуб в этом деле) 1.Вычислить произведение элементов массива S ,значение которых не больше заданного негативного числа A, а индексы нечетные(Кол.элементов:N=16;Элементы:от -9 до 4;A=-4;) 2.Найти количество одинаковых элементов которые находятся в массиве A(N). ( Кол.элементов:N=21;Элементы:от -4 до 4;) 3.Найти и напечатать, сколько не... подробнее

Показать сообщение отдельно
Shim
25 / 25 / 1
Регистрация: 21.11.2009
Сообщений: 159
22.12.2009, 19:03  [ТС]     Реализация алгоритма сортировки для любых типов данных
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(); // Ожидание нажатия на кнопку
}
 
Текущее время: 06:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru