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

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

Войти
Регистрация
Восстановить пароль
 
sort
1 / 1 / 0
Регистрация: 18.12.2010
Сообщений: 5
#1

не правильно расчитывает время сортировки и количество сравнений и присваений - C++

24.09.2011, 15:51. Просмотров 450. Ответов 1
Метки нет (Все метки)

Помогите разобраться в программе
не правильно расчитывает время сортировки и количество сравнений и присваений
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
#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
#include<stdio.h>
int dim, rep, n_comp, n_assign;
double t_prog;
int ar1[50], ar2[50], ar3[50];
int test_sorting(int arr, int arr_dim, int prog, long repeat);
int bubble_sort(int *b, int dim);
int insert_sort(int *b, int dim);
int select_sort(int *b, int dim);
int digit_sort(int *b, int dim);
int swap(int a, int b);
int assign(int a);
int menshe(int a, int b);
//int menshe_rav(int a, int b);
//int rav(int a, int b);
 int main()
{
clrscr();
int i, nom_arr, prog;
cout << "‚ўҐ¤ЁвҐ а*§¬Ґа*®бвм ¬*ббЁў*: ";
cin >> dim;
cout << "‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® Ї®ўв®аҐ*Ё© б®авЁа®ўЄЁ: ";
cin >> rep;
//Џ®бв஥*ЁҐ ¬*ббЁў®ў
//Ќ*з*«млҐ н«Ґ¬Ґ*вл ¬*ббЁў®ў
srand(time(NULL));//Ё*ЁжЁ*«Ё§*жЁп ¤*взЁЄ®ў б«гз*©*ле зЁбҐ«
ar1[0]=rand() % 1000;
ar2[0]=rand() % 1000;
ar3[0]=rand() % 100;
//Ћбв*«м*лҐ н«Ґ¬Ґ*вл
for (i=1; i<dim; i++)
{
ar1[i]=ar1[i-1]+1;
ar2[i]=ar2[i-1]-1;
ar3[i]=rand() % 100;
}
//ЏҐз*вм ¬*ббЁў®ў
for (i=0; i<dim; i++)
{
cout << ar1[i] << ' ';
cout << ar2[i] << ' ';
cout << ar3[i] << ' ';
}
//Џа®ўҐаЄ* Ї®¤Їа®Ја*¬¬ б®авЁа®ўЄЁ
nom_arr = 1;
while (nom_arr < 4 && nom_arr > 0)
{
cout << "“Є*¦ЁвҐ *®¬Ґа ¬*ббЁў*. „«п ®Є®*з**Ёп" << endl;
cout << "а*Ў®вл ўўҐ¤ЁвҐ ®ваЁж*⥫м*®Ґ зЁб«®: ";
cin >> nom_arr;
if (nom_arr < 0) return (0);
cout << " 1. Џг§ламЄ®ў*п б®авЁа®ўЄ* ";
cout << " 2. ‘®авЁа®ўЄ* ўбв*ўЄ®©";
cout << " 3. ‘®авЁа®ўЄ* ўлЎ®а®¬";
cout << " 4. Џ®а*§ап¤**п б®авЁа®ўЄ* ";
cout << " “Є*¦ЁвҐ *®¬Ґа Їа®Ја*¬¬л б®авЁа®ўЄЁ: ";
cin >> prog;
n_assign = 0; n_comp = 0;
test_sorting(nom_arr, dim, prog, rep);
cout << endl << endl << "Time = ";
cout.setf(ios::scientific);
cout << t_prog;
cout.unsetf(ios::scientific);
cout << "¬б. ЏаЁбў®Ґ*Ё© - " <<(n_assign / rep / rep);
cout << ". ‘а*ў*Ґ*Ё© - " << (n_comp / rep / rep) << endl;
 }
return 0;
 }
int test_sorting(int arr_no, int arr_dim, int prog, long repeat)
{
long i,j; int k;
int ar[100];
time_t time0, time1;
time0 = time(NULL);//Њ®¬Ґ*в **з*«* а*Ў®вл Ї®¤Їа®Ја*¬¬л
for (i=0; i<repeat; i++)
for (j=0; j<repeat; j++)
{
//‚®ббв**®ў«Ґ*ЁҐ гЇ®а冷稢*Ґ¬®Ј® ¬*ббЁў*
switch (arr_no)
{
case 2:
for (k=0; k<arr_dim; k++)
ar[k]=ar2[k];
break;
case 3:
for (k=0; k<arr_dim; k++)
ar[k]=ar3[k];
break;
default:
for (k=0; k<arr_dim; k++)
ar[k]=ar1[k];
break;
}
//‚лЎ®а Їа®Ја*¬¬л
switch (prog)
{
case 2:
insert_sort(ar,arr_dim);
break;
case 3:
select_sort(ar,arr_dim);
break;
case 4:
digit_sort(ar,arr_dim);
break;
default:bubble_sort(ar,arr_dim);
break;
}
}
time1 = t_prog;//Њ®¬Ґ*в Є®*ж* а*Ў®вл Ї®¤Їа®Ја*¬¬л
t_prog = (time1 - time0)*1000;//*1000*1000/((double)repeat)/((double)repeat);
cout << endl << endl;
for (i=0; i<arr_dim; i++)
cout << ar[i] << ' ';
 return 0;
}
 int bubble_sort(int *b, int dim)
{
int i,j,mmm;
for (i=1; i<dim; i++)
for (j=1; j<=dim-i; j++)
if (menshe(b[j], b[i-1])) //b[j-1] > b[j]
{
mmm=assign(b[j-1]);
b[j-1]=assign(b[j]);
b[j]=assign(mmm);
}
return(0);
}
int insert_sort(int *b, int dim)
{
int i,j,mmm;
for (i=1; i<dim; i++)
{
mmm=b[i];
n_assign++;
//ќ«Ґ¬Ґ*вл ¬*ббЁў* ¤® i-Ј®ЎЄ®в®алҐ Ў®«миҐ b[i] б¤ўЁЈ*овбп ўЇа*ў®
for (j=i; j>0 && menshe(mmm, b[j-1]);j--)
{
b[j]=b[j-1];
n_assign++;
}
b[j]=mmm;
n_assign++;
}
return(0);
}
int select_sort(int *b, int dim)
{
int i, j, i_min, mmm;
for (i=0; i<dim-1; i++)
{
i_min=i;
n_assign++;
for (j=i+1; j<dim; j++)
 if (menshe(b[j], b[i_min])) //b[j] < b[i_min]
{
 i_min=j;
n_assign++;
 }
mmm = assign(b[i_min]);
b[i_min] = assign(b[i]);
 b[i] = assign(mmm);
}
return(0);
}
//Џ®а*§ап¤**п б®авЁа®ўЄ*
 int digit_sort(int* b, int dim)
{
int dg_add(int *c1, int *c2, int dim, int pos);
int i, div;
int bb[100];
div = 1;
for (i=0; i<4; i++)
{
dg_add(b,bb,dim,div);
 div *= 10;
dg_add(bb,b,dim,div);
div *= 10;
}
return(0);
}
 int dg_add(int *c1, int *c2, int dim, int div)
{
int i, k;
int cnt[11];
//Џ®бзҐв Є®«ЁзҐбвў* зЁбҐ«
for (i=0; i<11; i++) cnt[i]=0;
for (i=0; i<dim; i++)
 {
 k=(c1[i] / div) % 10;
cnt[k+1]++;
 n_assign++;
}
 for (i=1; i<11; i++)
 {
 cnt[i]+=cnt[i-1]; //дг*ЄжЁп §*ЇЁбЁ
 n_assign++;
 }
 for (i=0; i<dim; i++)//Џ®бваҐ*ЁҐ
{
k=(c1[i] / div) % 10;
c2[cnt[k]++] = c1[i];
n_assign++;
}
return(0);
}
int assign(int a)
{
n_assign++;
return a;
}
int menshe(int a, int b)
 {
 n_comp++;
 if (a<b) return(1);
 else return(0);
 }
int rav(int a, int b)
{
n_comp++;
if (a==b) return(1);
else return(0);
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2011, 15:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос не правильно расчитывает время сортировки и количество сравнений и присваений (C++):

Найти количество сравнений после сортировки массива - C++
Нужно чтобы писала количество сравнений после сортировки массива, но я вроде все прописал #include &quot;stdafx.h&quot; #include...

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

Модифицировать код сортировки так, чтобы на каждом следующем проходе количество сравнений декрементировалось - C++
Помогите разобраться. Нужно модифицировать так, чтобы на втором проходе было 8 сравнений, на третьем 7 и т.д. #include &lt;iostream&gt; ...

Счетчик сравнений для быстрой сортировки - C++
Добрый вечер. Взял сортировку из википедии void qSort(int arr7, int first, int last) { k = first; l =...

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

График зависимость количества перестановок и сравнений от размерности массива для алгоритмов сортировки - C++
имеются массивы с размерностью от 1 до 20 с данными не отсортированными,частично отсортированными ,отсортированными в обратную сторону...

1
Thinker
24.09.2011, 16:05     не правильно расчитывает время сортировки и количество сравнений и присваений
  #2

Не по теме:

Обычно сложность алгоритма вычисляется теоретически, а не эмпирически

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2011, 16:05
Привет! Вот еще темы с ответами:

Два счетчика для обмена и сравнений для сортировки массива - C++
написал два счетчика для обмена и сравнений для сортировки массива.Проблема при выводе выводится сначала кучу чисел сортировки и обмена,а...

Где правильно ставить счетчики сравнений и перестановок, и как считать сложность этих алгоритмов? - C++
написал код двух сортировок, но не уверен, что правильно проставлены счетчики.#include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;conio.h&gt; ...

Количество сравнений в массиве - C++
И снова здравствуйте!) Есть рабочий код - поиск в двоичном массиве. Как модифицировать код, чтоб вычислить число сравнений при поиске?? ...

Количество обменов и сравнений в HeapSort - C++
Всем доброго времени суток! :) Помогите, пожалуйста, разобраться с задачей. Мне нужно подсчитать количество обменов и сравнений в...


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

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

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