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

Сортировки - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Шаблон http://www.cyberforum.ru/cpp-beginners/thread191476.html
Всем доброе время суток)) Вот нпаисал прогу: #include <string.h> #include <iostream> using namespace std; template<class T> class List{ private: struct Element{
C++ Дано число n. Найти сумму n-значных чисел Кто может решит такую задачу. Дано число n. Найти сумму n-значных чисел. Ограничениа 0<n<=100. Хочу сказать что эту задачу я решил, просто интересно кто кокой алгоритм придложет. http://www.cyberforum.ru/cpp-beginners/thread191461.html
C++ Удаление узла бинарного дерева
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include <iostream> using namespace std; #include "TreeNode.h" int main(void) { TreeNode ob(3); ob.AddElement(5);
C++ Это массив?
static int attrListSgl = {GLX_RGBA, GLX_RED_SIZE, 4, GLX_GREEN_SIZE, 4, GLX_BLUE_SIZE, 4, GLX_DEPTH_SIZE, 16, None}; Это массив?
C++ Что это структура? http://www.cyberforum.ru/cpp-beginners/thread191425.html
#include<stdio.h> #include<stdlib.h> #include<X11/X.h> #include<X11/Xlib.h> #include<GL/gl.h> #include<GL/glx.h> #include<GL/glu.h> Display *dpy; Window root;
C++ delete или new (typeid(void*))(void*) Доброе время суток. Пишу список. Телом каждого элемента (el) списка является void указатель(body). (предполагается что тело элемента может быть любого типа, т.е. переменные, классы, другой такой же список и т.д.) Критерий - универсальность и скорость. У меня получилось что-то типа (*el).body = new typeid(NewType); где NewType - параметр функции, void * на какую либо известную переменную... подробнее

Показать сообщение отдельно
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 22:30     Сортировки
Ну тогда для полноты картины:
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
/*Программа сортирует обменом на расстоянии, Пирамидальной сортировкой и сортировкой вставками
случайную, обратно-упорядоченную, упорядоченную и квазиупорядоченную последовательности
 вещественных чисел разных размеров. Выводит время сортировки и количество операций сравнения.
 Выполнил */
#include <iostream>
#include <conio.h>
#include <cstdlib>
#include <windows.h>
#include <cmath>
#include <iomanip>
 
using namespace std;
//----------- Функции генерации последовательностей -------------------------
void up_double( double *Array, double min, double max, int size);
void ob_up_double( double *Array, double min, double max, int size);
void rnd_double(double *Array, double max, double min, int Size);
void kvazi_double( double *Array, double min, double max, int size);
//----------- Функции сортировки ---------------------------------------
void sort_puz(double *Array, int size, int step, int l);
void ShellPuzir(double* Array, int size);
void InSort(double *Array, int n);
void piramida(double* Array,int size);
void pros (double* Array, int k, int size);
//---------------- Функция тестирования времени выполнения ---------------
void wTime (void SortFunction(double*, int), void Generate(double*, double, double, int), double* Array);
//----------------- Вспомогательные функции---------------------------
char* RUS(const char* text);
char Buf[128];
bool prov(double* Array, int size);
void obm(double& a, double& b);
bool bolshe(double a, double b);
bool menshe(double a,double b);
double z;//глобальная переменная для подсчета количества операций сравнения
 
int main()
{   
    void (*SortFunction)(double*, int);//Указатель на функцию сортировки
    void (*Generate)(double*, double, double, int);//  Указатель на функцию генерации
    int n=0, size = 250000;
    double A[250000];
    double* Array = A;
    /////////////////////   Случайная последовательность /////////////////////////////
    cout << RUS("Сортировка обменом на расстоянии случайной последовательности: ") << endl;
    SortFunction = ShellPuzir;
    Generate = rnd_double;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //---------------------------------
    cout << RUS("Пирамидальная сортировка случайной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками случайной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    /////////// Обратно упорядоченная последовательность   //////////////////////////////
    Generate = ob_up_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии обратно упорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка обратно упорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками обратно упорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    ////////////////////////// Упорядоченная последовательность   //////////////////////
    Generate = up_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии упорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка упорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками упорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    /////////////////// Квазиупорядоченная последовательность   ///////////////////////*/
    Generate = kvazi_double;
    SortFunction = ShellPuzir;
    cout << RUS("Сортировка обменом на расстоянии квазиупорядоченной последовательности");
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";  
    //---------------------------------
    cout << RUS("Пирамидальная сортировка квазиупорядоченной последовательности: ") << endl;
    SortFunction = piramida;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для продолжения нажмите любую клавишу") << endl;
    getch();
    cout << "********************************************************\n";
    //--------------------------------
    SortFunction = InSort;
    cout << endl << RUS("Сортировка вставками квазиупорядоченной последовательности:  ") << endl;
    wTime(SortFunction, Generate, Array);
    cout << RUS("Для выхода из программы нажмите любую клавишу") << endl;
    getch();
    return 0;
}
 
//////////Генерация упорядоченной последовательности ///////////////
void up_double( double *Array, double min, double max, int size)
 {
  for(int i=0;i<=size;++i)
  Array[i]=min +((max-min)/size)*i;
 }
///// Генерация последовательности случайных чисел///////////////
void rnd_double(double *Array, double max, double min, int Size)
{
    srand(time(NULL));
    for( int i = 0; i<Size; ++i)
       Array[i] = min + (max-min)*((double) rand()/RAND_MAX);
}
 
///// Генерация обратно-упорядоченной последовательности///////////
  void ob_up_double( double *Array, double min, double max, int size)
 {
  for(int i=0;i<size;++i)
  Array[i]=max -((max-min)/(size-1))*i;
 }        
 
//////////Генерация квазиупорядоченной последовательности//////////          
void kvazi_double( double *Array, double min, double max, int size)
 {
  int proc, i;
  for(i=0;i<size;++i)
    Array[i]=min +((max-min)/size)*i;
  proc = (int)ceil(0.05*size);
  srand(time(NULL));
  for (i=0; i<proc; ++i)
    Array[rand()%size] = min + (max-min)*((double) rand()/RAND_MAX);
 }
 //////Функция проверки массива на упорядоченность//////////////
bool prov(double* Array, int size)
 {
     for (int i=1;i<size;i++)
     { 
         if(Array[i]<Array[i-1])
             return false;
     }
     return true;
}
 
////////Для вывода русских букв////////////
char*RUS(const char* text)
 {
  CharToOem(text, Buf);
  return Buf;
 }
///////  Функция обмена   /////////////////
 void obm(double& a, double& b)
{    
     double temp = a;
     a = b;
     b = temp;
}
 
 /////////////Функция сортировки методом пузырька////////////////
 void sort_puz(double *Array, int size, int step, int l)
 {
     int i, j, n;
     for (i=0;i<(size-l)/step;i++)
     {
         n = 0;
         for(j=step+l;j<size;j+=step)
         {
              if (menshe(Array[j], Array[j-step]))
              { 
                     obm(Array[j],Array[j-step]);
                     n++;
              }
         }
         if(n == 0)//если при очередном проходе перестановок не было, то массив упорядочен
         break;
     }
     
 } 
 
 
 ///////////////////Функция сортировки обменом на расстоянии///////////////////
 //step[] - Массив последовательности шагов 1, 4, 9 ...
void ShellPuzir(double* Array, int size)
{
     int step[11],l;
     step[0] = 1;
     for(int i = 1;i < 11;i++)//заполнение массива шагов
        step[i] = step[i - 1]*3  + 1;
     for (int t = 10; t > 0;t--)//изменяет значение шага
        for( l = 0;l<step[t] && (step[t]+l)<size;l++)//цикл t-упорядочивает файл
           sort_puz (Array,size,step[t],l);//внутри t - файла сортируем обменом
     InSort(Array,size); //окончательная сортировка вставкими    
}
 
////////////////////////Функция сортировки вставками////////////////
void InSort(double *Array, int n)
 {
      int i,j,h=1;
      double t;
      for (i=h;i<n;i+=h)
      {
          j = i;
          t = Array[i];
          while(j>0 && menshe(t,Array[j-h]))
          {
                    Array[j] = Array[j-h];
                    j-=h;
          }
          Array[j] = t;
      }
 }
 ////////// Функция пирамидальной сортировки   //////////////////////
 void piramida(double* Array,int size)
{
     int k;
     int n = size-1;//индекс последнего элемента
     for( k = n/2;k>=0;k--)
        pros(Array,k,size);//просеиваем весь массив, a[0] - max
     while (n > 0)
     {     
           obm(Array[0], Array[n]);//ставим максимальный элемент в конец массива
           n--;//и больше его не трогаем
           pros(Array, 0, n+1);//просеиваем первый элемент
     }
}
 
/////  Функция просеивания элемента сквозь пирамиду   /////////////////
void pros (double* Array, int k, int size)
{
   int l, n = size - 1;
   while (2*k+1 <= n)
   {
         l = 2*k+1;
         if(l<n && menshe(Array[l], Array[l+1]))
         l++;                        // l - наибольший из сыновей k
         if (!(menshe(Array[k], Array[l])))//если родитель >= сын, то выходим из цикла
         break;
         obm(Array[k], Array[l]);//иначе меняем их местами
         k = l;
   }
}
 
 
 ////////// Функция тестирует и выводит на экран время выполнения функций сортировки и количество сравнений///////
void wTime (void SortFunction(double*, int), void Generate(double*, double, double, int), double* Array)
{
     SYSTEMTIME st1,st2;
     int size2[] = { 10000, 25000400005000075000100000, 150000, 200000, 250000};//массив размеров
     for(int j=0;j<9;j++)
   { 
     Generate(Array,-100000,100000,size2[j]);//генерируем последовательность
     z = 0;
     GetLocalTime(&st1);
       SortFunction(Array, size2[j]);  //сортируем
     GetLocalTime(&st2);
     double T1 = (double)(st1.wMinute*60*1000 + st1.wSecond*1000 + st1.wMilliseconds); //вычисляем время
     double T2 = (double)(st2.wMinute*60*1000 + st2.wSecond*1000 + st2.wMilliseconds);
     cout << endl << RUS("Для size = ") << size2[j] << "   \n" ;
     cout << RUS("время выполнения функции: ");
     cout << (T2 - T1) << RUS("   Миллисекунд") << endl;
     cout.setf(ios::fixed);
     cout << setprecision(0) << RUS("Количество операций сравнения: ") << z;
    if(prov(Array,size2[j]))
      cout << RUS("\nУпорядоченная") << endl;
    else
      cout << RUS("\nНеупорядоченная") << endl;
      cout << "-----------------------------------------------------------\n";
   }
}
//////// Функция "Больше" с инкрементом//////////////
bool bolshe(double a, double b)
 {
      z++;
      if (a>b)
       return true;
      else
       return false;
}
 
/////////Функция "Меньше" с инкрементом ////////////////
bool menshe(double a, double b)
 {
      z++;
      if (a<b)
       return true;
      else
       return false;
}
 
Текущее время: 03:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru