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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.71
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
#1

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

15.11.2010, 13:33. Просмотров 2175. Ответов 27
Метки нет (Все метки)

Есть динамичный массив:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <ctime>
 
using namespace std;
 
int main() {
    setlocale(LC_ALL,"Russian");  
    srand((unsigned)time(NULL));
    int *arr;
    int size;
    cout << "Введите размер массива: ";
    cin >> size;
    arr = new int[size];    
    cout << "Сформированый массив: ";
    for(int i = 0; i < size; i++) {
        arr[i] = rand() % 9 + 1;
        cout << arr[i] << "  ";
    }   
    cout << endl;   
    delete [] arr;
    system("pause");
}
Мне надо его отсортировать 5 способами:
Insertion sort
Selection sort
Merge sort
Bubble sort
Quick sort
Уважаемые оставляйте комментарии в коде. В заранее благодарю.
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.11.2010, 13:33
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировки (C++):

Составить блок – схемы для шейкер- сортировки и сортировки Шелла - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить блок – схемы для шейкер-...

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

Составить программы для пузырьковой сортировки и сортировки посредством выбора с применением оператора while - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить программы для пузырьковой...

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

Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее а - C++
Напишите функцию сортировки, похожую на функцию которая использовалась для сортировки массивов, с той разницей, что ее аргументом должен...

Изменить метод "быстрой сортировки" на метод "сортировки вставками" - C++
Как изменить метод &quot;интеративной быстрой сортировки&quot; на метод &quot;сортировки вставками «с конца массива»&quot;? Нужно изменить только метод...

27
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 21:09 #16
quicksort - быстрая сортировка
MergeSort - сортировка слиянием

Добавлено через 1 минуту
Вот SelectionSort...
Молодец!

Добавлено через 1 минуту
Цитата Сообщение от Temirlan90 Посмотреть сообщение
криво работает =(
разбирайся:-)
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:15  [ТС] #17
Посмотрел пирамидальную сортировку и сортировку слияния. Вот их плюсы в гибридной сортировке
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void Merge(int const *const A, int const nA,
            int const *const B, int const nB,
            int *const C) { //Выполнить слияние массива A, содержащего nA элементов,
                            //  и массива B, содержащего nB элементов.
                            //  Результат записать в массив C.
                int a(0), b(0); //Номера текущих элементов в массивах A и B
                while( a + b < nA + nB ) { //Пока остались элементы в массивах
                    if( (b >= nB) || ( (a < nA) && (A[a] <= B[b]) ) ) { //Копирую элемент из массива A
                        C[a + b] = A[a];
                        a++;
                    } 
                    else { //Копирую элемент из массива B
                        C[a + b] = B[b];
                        b++;
                    }
                }
}
 
void SiftDown(int* const heap, int i, int const n) {   
    //Просеивает элемент номер i вниз в пирамиде heap.
    //n -- размер пирамиды
    //Идея в том, что вычисляется максимальный элемент из трёх:
    //  1) текущий элемент
    //  2) левый потомок
    //  3) правый потомок
    //Если индекс текущего элемента не равен индексу максималь-
    //  ного, то меняю их местами, и перехожу к максимальному
    //Индекс максимального элемента в текущей тройке элементов:
    int nMax(i);
    //Значение текущего элемента (не меняется):
    int const value(heap[i]);
    while (true) { 
        //Рассматривается элемент i и его потомки i*2+1 и i*2+2
        //В начале каждой итерации nMax == i и value == heap[i]
        int childN(i * 2 + 1); //Индекс левого потомка
        //Если есть левый потомок и он больше текущего элемента,
        if ((childN < n) && (heap[childN] > value))
            nMax = childN; //  то он считается максимальным
            ++childN; //Индекс правого потомка
            //Если есть правый потомок и он больше максимального,
            if ((childN < n) && (heap[childN] > heap[nMax]))
                nMax = childN; //  то он считается максимальным
            //Если текущий элемент является максимальным из трёх
            //  (т.е. если он больше своих детей), то конец:
            if (nMax == i) break;
            //Меняю местами текущий элемент с максимальным:
            heap[i] = heap[nMax]; heap[nMax] = value;
            //  при этом значение value будет в ячейке nMax,
            //  поэтому в начале следующей итерации значение value
            //  правильно, т.к. мы переходим именно к этой ячейке
            //Переходим к изменившемуся потомку
            i = nMax;
    }
}
 
void HeapSort(int* const heap, int n) {   //Пирамидальная сортировка массива heap.
    //  n -- размер массива 
    //Этап 1: построение пирамиды из массива
    for(int i(n / 2 - 1); i >= 0; --i) SiftDown(heap, i, n);
    //Этап 2: сортировка с помощью пирамиды.
    //Здесь под «n» понимается размер пирамиды
    while(n > 1) { //Пока в пирамиде больше одного элемента
        --n; //Отделяю последний элемент
        //Меняю местами корневой элемент и отделённый:
        int const firstElem(heap[0]);
        heap[0] = heap[n];
        heap[n] = firstElem;
        //Просеиваю новый корневой элемент:
        SiftDown(heap, 0, n);
    }
}
 
void HybridSort(int *&A, int n) { 
    //Отсортировать массив A, содержащий n элементов.
    //При работе указатель на A, возможно, меняется.
    //(Функция получает ссылку на указатель на A)   
    //Размер кусочка для сортировки пирамидой:
    //(нужно подбирать для максимального ускорения)
    int const tileSize(4096);
    for(int start(0); start < n; start += tileSize)
        HeapSort(A + start, min(tileSize, n - start));
    if(n <= tileSize) return; //Больше сортировать не нужно
    int *B(new int[n]); //Временный буфер памяти
    for(int size(tileSize); size < n; size *= 2) { 
        //Перебираем размеры кусочков для слияния,
        //  начиная с tileSize элементов
        int start(0); //Начало первого кусочка пары
        for(;(start + size) < n; start += size * 2) {
            //Перебираем все пары кусочков, и выполняем попарное
            //  слияние. (start+size)<n означает, что начало
            //  следующего кусочка лежит внутри массива
            Merge(A + start, size, A + start + size, min(size, n - start - size), B + start);
        }
        //Если последний кусочек остался без пары, просто копируем
        //его из A в B:
        for(; start < n; start++) B[start] = A[start];
        int *temp(B); B = A; A = temp; //Меняем местами указатели
    }
    delete[n] B; //Удаляем временный буфер
}
 
int main() {
        setlocale(LC_ALL,"Russian");  
        srand((unsigned)time(NULL));
        int *arr;
        int size;       
        cout << "Введите размер массива: ";
        cin >> size;
        arr = new int[size];        
        cout << "Сформированый массив: ";
        for(int i = 0; i < size; i++) {
                arr[i] = rand() % 100;
                cout << arr[i] << "  ";
        } 
        cout << endl;
        HybridSort(arr, size);      
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
все легко, когда вникнешь =) Кстати эту сортировку можно бы и добавить в FAQ.
1
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 21:27 #18
Цитата Сообщение от Temirlan90 Посмотреть сообщение
все легко, когда вникнешь =)
Ну вот видишь!
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 21:28  [ТС] #19
Естественная сортировка:
Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные.
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
#include <iostream>
#include <ctime>
 
using namespace std;
 
void Merge(int const *const A, int const nA,
            int const *const B, int const nB,
            int *const C) { //Выполнить слияние массива A, содержащего nA элементов,
                            //  и массива B, содержащего nB элементов.
                            //  Результат записать в массив C.
                int a(0), b(0); //Номера текущих элементов в массивах A и B
                while( a + b < nA + nB ) { //Пока остались элементы в массивах
                    if( (b >= nB) || ( (a < nA) && (A[a] <= B[b]) ) ) { //Копирую элемент из массива A
                        C[a + b] = A[a];
                        a++;
                    } 
                    else { //Копирую элемент из массива B
                        C[a + b] = B[b];
                        b++;
                    }
                }
}
 
void NaturalSort(int *&A, int  n) { 
    //Отсортировать массив A, содержащий n элементов.
    //При работе указатель на A, возможно, меняется.
    //(Функция получает ссылку на указатель на A)
    int *B(new int[n]); //Временный буфер памяти
    while(true) {
        //Выполняем слияния, пока не останется один
        //отсортированный участок. Выход из цикла
        //находится дальше
        int start1, end1; //Первый отсортированный участок
        int start2(-1), end2(-1); //Второй отсортированный участок
        while(true) { 
            //Цикл по всем парам отсортированных участков в массиве           
            //Начало первого участка для слияния находится после
            //конца второго участка предыдущей пары:
            start1 = end2 + 1; end1 = start1;
            //Двигаемся вправо до нарушения сортировки:
            while((end1 < n - 1) && (A[end1] <= A[end1 + 1])) end1++;
            //Первый участок пары простирается до конца массива:
            if(end1 == n - 1) break;           
            //Начало второго участка для слияния находится после
            //конца первого участка текущей пары:
            start2 = end1 + 1, end2 = start2;       
            //Двигаемся вправо до нарушения сортировки:
            while((end2 < n - 1) && (A[end2] <= A[end2 + 1])) end2++;
            //Выполняем слияние двух отсортированных участков
            Merge(A + start1, end1 - start1 + 1,
                    A + start2, end2 - start2 + 1,
                    B + start1);
            //Второй участок пары простирается до конца массива:
            if(end2 == n - 1) break;
        }
        //Данные полностью отсортированы и находятся в массиве A:
        if(( start1 == 0) && (end1 == n - 1)) break;       
        //Если последний кусочек остался без пары, просто копируем
        //его из A в B:
        if(end1 == n - 1) {
            for(; start1 < n; start1++) B[start1] = A[start1];
        }
        int *temp(B); B = A; A = temp; //Меняем местами указатели
    }
    delete[n]B; //Удаляем временный буфер
}
 
int main() {
        setlocale(LC_ALL,"Russian");  
        srand((unsigned)time(NULL));
        int *arr;
        int size;       
        cout << "Введите размер массива: ";
        cin >> size;
        arr = new int[size];        
        cout << "Сформированый массив: ";
        for(int i = 0; i < size; i++) {
                arr[i] = rand() % 100;
                cout << arr[i] << "  ";
        } 
        cout << endl;
        NaturalSort(arr, size);     
        cout << "\nОтсортированный массив: ";
        for(int i = 0; i < size; i++) {
                cout << arr[i] << "  ";
        }           
        delete [] arr;
        system("pause");
}
2
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 22:30 #20
Ну тогда для полноты картины:
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;
}
1
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
15.11.2010, 22:36  [ТС] #21
RUSya82, у меня на VS2010 не компилируется=( Вы на каком компиляторе запускали?
Unhandled exception at 0x00413ed7 in rr.exe: 0xC00000FD: Stack overflow.
0
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
15.11.2010, 23:03 #22
Dev C++ 4.9.9.2
Компилируется нормально

Добавлено через 23 секунды
Переполнение стека у Вас

Добавлено через 2 минуты
Объявите double A[250000]; из 40 строки глобально, то есть вне функции main(). Должно пойти.
1
isaak
103 / 40 / 9
Регистрация: 17.10.2010
Сообщений: 665
15.11.2010, 23:39 #23
RUSya82, а почему у меня компилятор ругается:
Error 1 error C2084: function 'int main(void)' already has a body c:\program files\microsoft sdks\windows\v6.0a\include\bcrypt.h 3 p786
Error 2 error C2146: syntax error : missing ';' before identifier 'NCryptBuffer' c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 111 p786
Error 3 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 111 p786
Error 4 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 111 p786
Error 5 error C2146: syntax error : missing ';' before identifier 'NCryptBufferDesc' c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 113 p786
Error 6 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 113 p786
Error 7 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 113 p786
Error 8 error C2061: syntax error : identifier 'NCryptBufferDesc' c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 447 p786
Error 9 error C2061: syntax error : identifier 'NCryptBufferDesc' c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 461 p786
Error 10 error C2061: syntax error : identifier 'NCryptBufferDesc' c:\program files\microsoft sdks\windows\v6.0a\include\ncrypt.h 557 p786
Error 11 error C2146: syntax error : missing ';' before identifier 'hCNGContentEncryptKey' c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8161 p786
Error 12 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8161 p786
Error 13 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8161 p786
Error 14 error C2146: syntax error : missing ';' before identifier 'hCNGContentEncryptKey' c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8542 p786
Error 15 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8542 p786
Error 16 error C4430: missing type specifier - int assumed. Note: C++ does not support default-int c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 8542 p786
Error 17 error C2061: syntax error : identifier 'BCRYPT_KEY_HANDLE' c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 14115 p786
Error 18 error C2061: syntax error : identifier 'BCRYPT_KEY_HANDLE' c:\program files\microsoft sdks\windows\v6.0a\include\wincrypt.h 14129 p786
Error 19 error C3861: 'time': identifier not found c:\users\администратор\documents\visual studio 2008\projects\c++\console\p786\p786\p786.cpp 141 p786
Error 20 error C3861: 'time': identifier not found c:\users\администратор\documents\visual studio 2008\projects\c++\console\p786\p786\p786.cpp 160 p786
0
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
16.11.2010, 13:32 #24
хы, не знаю. я ВС не пользуюсь. Но в Dev c++ все ОК

Добавлено через 1 минуту
Цитата Сообщение от isaak Посмотреть сообщение
ncrypt.h
Это кто?

Добавлено через 3 часа 31 минуту
isaak, Мне кажется у вас какие то проблемы с CharToOem

Добавлено через 8 часов 12 минут
Temirlan90, Запустилась программа?
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
16.11.2010, 14:11  [ТС] #25
Столкнулся с двумя видами поиска (Бинарный и Линейный), вот собственно исходники:
Бинарный (рекурсивный и не рекурсивный)
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
#include <stdio.h>
#include <conio.h>
#define MAX_LEN 10
 
/* Non-Recursive function*/
void b_search_nonrecursive(int l[],int num,int ele) {
    int l1, i, j, flag = 0;
    l1 = 0;
    i = num - 1;
    while(l1 <= i) {
        j = (l1 + i) / 2;
        if( l[j] == ele) {
            printf("\nThe element %d is present at position %d in list\n", ele, j);
            flag = 1;
            break;
        }
        else
            if(l[j] < ele)
                l1 = j + 1;
            else
                i = j - 1;
    }
    if( flag == 0)
        printf("\nThe element %d is not present in the list\n", ele);
}
 
/* Recursive function*/
int b_search_recursive(int l[], int arrayStart, int arrayEnd, int a) {
    int m, pos;
    if (arrayStart <= arrayEnd) {
        m = (arrayStart + arrayEnd) / 2;
        if (l[m] == a)
            return m;
        else 
            if (a < l[m])
                return b_search_recursive(l, arrayStart, m - 1, a);
            else
                return b_search_recursive(l, m + 1, arrayEnd, a);
    }
    return -1;
}
 
void read_list(int l[], int n) {
    int i;
    printf("\nEnter the elements:\n");
    for(i = 0; i < n; i++)
        scanf("%d", &l[i]);
}
 
void print_list(int l[], int n) {
    int i;
    for(i = 0; i < n; i++)
        printf("%d\t", l[i]);
}
 
/*main function*/
void main() {
    int l[MAX_LEN], num, ele, f, l1, a;
    int ch, pos;
    printf("======================================================");
    printf("\n\t\t\tMENU");
    printf("\n=====================================================");  
    printf("\n[1] Binary Search using Recursion method");  
    printf("\n[2] Binary Search using Non-Recursion method");  
    printf("\n\nEnter your Choice:");  
    scanf("%d",&ch); 
    if(ch <= 2 & ch > 0) { 
        printf("\nEnter the number of elements : ");  
        scanf("%d", &num);  
        read_list(l, num);  
        printf("\nElements present in the list are:\n\n");  
        print_list(l, num);  
        printf("\n\nEnter the element you want to search:\n\n");  
        scanf("%d", &ele);     
        switch(ch) {
        case 1:printf("\nRecursive method:\n");  
            pos = b_search_recursive(l, 0, num, ele);  
            if(pos == -1) {  
                printf("Element is not found");  
            }  
            else {  
                printf("Element is found at %d position", pos);  
            }  
            getch();   
            break;
        case 2:printf("\nNon-Recursive method:\n"); 
            b_search_nonrecursive(l, num, ele);
            getch();
            break;
        }
    }
    getch(); 
}
Линейный(рекурсивный и не рекурсивный)
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
#include <stdio.h>  
#include <conio.h>
#define MAX_LEN 10 
 
/* Non-Recursive method*/
void l_search_nonrecursive(int l[], int num, int ele) {
    int j, f = 0;
    for(j = 0; j < num; j++)
        if( l[j] == ele) {
            printf("\nThe element %d is present at position %d in list\n", ele, j);
            f = 1;
            break;
        }
        if(f == 0)
            printf("\nThe element is %d is not present in the list\n", ele);
}
 
/* Recursive method*/
void l_search_recursive(int l[], int num, int ele) {
    int f = 0;
    if( l[num] == ele) {
        printf("\nThe element %d is present at position %d in list\n", ele, num);  
        f = 1;
    }
    else {
        if((num == 0) && (f == 0)) {
            printf("The element %d is not found.", ele);
        }
        else {
            l_search_recursive(l, num - 1, ele);
        }
    }
    getch();
}
 
void read_list(int l[], int num) {
    int j;
    printf("\nEnter the elements:\n");
    for(j = 0; j < num; j++)
        scanf("%d", &l[j]);
}
 
void print_list(int l[], int num) {
    int j;
    for(j = 0; j < num; j++)
        printf("%d\t", l[j]);
} 
 
void main() {
    int l[MAX_LEN], num, ele;
    int ch;    
    printf("======================================================");  
    printf("\n\t\t\tMENU");  
    printf("\n=====================================================");  
    printf("\n[1] Linary Search using Recursion method");  
    printf("\n[2] Linary Search using Non-Recursion method");  
    printf("\n\nEnter your Choice:");  
    scanf("%d", &ch);    
    if(ch <= 2 & ch > 0) { 
        printf("Enter the number of elements :");  
        scanf("%d", &num);  
        read_list(l, num);  
        printf("\nElements present in the list are:\n\n");  
        print_list(l, num);  
        printf("\n\nElement you want to search:\n\n");  
        scanf("%d", &ele);    
        switch(ch) {  
        case 1:printf("\n**Recursion method**\n");  
            l_search_recursive(l, num, ele);  
            getch();  
            break;  
        case 2:printf("\n**Non-Recursion method**\n");  
            l_search_nonrecursive(l, num, ele);
            getch();  
            break;  
        }  
    }  
    getch();  
}  
/*end main*/
Кто нибудь расставите комментарии в двух данных исходниках. Заранее спасибо =)

Добавлено через 24 минуты
Temirlan90, Запустилась программа?
да, спасибо

RUSya82, как я понял, вы там все алгоритмы сравнивали которые я выкладывал?
0
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
16.11.2010, 21:32 #26
Цитата Сообщение от Temirlan90 Посмотреть сообщение
RUSya82, как я понял, вы там все алгоритмы сравнивали которые я выкладывал?
Нет, я просто предлагал свои решения.

Добавлено через 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
/* Non-Recursive function*/
/*num - количество элементов
ele - поисковый элемент*/
void b_search_nonrecursive(int l[],int num,int ele) {
        int l1, i, j, flag = 0;
        l1 = 0;
        i = num - 1;
        while(l1 <= i) {//продолжаем, пока поиск не сузится до 1 элемента
                j = (l1 + i) / 2;//Делим массив пополам
                if( l[j] == ele) {//если середина и есть поисковый элемент, тогда говорим об этом
                        printf("\nThe element %d is present at position %d in list\n", ele, j);
                        flag = 1;
                        break;
                }
                else
                        if(l[j] < ele)//иначе выбираем для поиска тот полумассив, где вероятно находится
                                      //поисковый элемент
                                l1 = j + 1;
                        else
                                i = j - 1;
        }
        if( flag == 0)//если флаг не установлен, то элемент не найден
                printf("\nThe element %d is not present in the list\n", ele);
}
Добавлено через 8 минут
Ну а в линейном поиске итак все понятно, просто смотрим весь массив подряд, и проверяем, нет ли там поискового элемента)
1
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.11.2010, 18:52  [ТС] #27
RUSya82, а как можно добавить туда что бы считало сколько мили секунд тратится на поиск?)
0
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
17.11.2010, 21:22 #28
Можно. Так же, как и при сортировке. Объявляете две переменных типа SYSTEMTIME. например SYSTEMTIME st1, st2;
Функция GetLocalTime(&st1) - запишет в переменную текущее время. Т.о. записываешь время до запуска функции и после. То есть:
C++
1
2
3
GetLocalTime(&st1);
Function();
GetLocalTime(&st2);
Потом вычисляешь время и выводишь результат:
C++
1
2
3
4
5
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;
1
17.11.2010, 21:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2010, 21:22
Привет! Вот еще темы с ответами:

Си++, Сортировки - C++
Написать программу, осуществляющую блочную сортировку одномерного массива

Сортировки С++ - C++
Всем доброго времени суток! Не могу понять в чем ошибка,прошу помочь. вот условие задачи: В текстовом файле содержатся записи о...

сортировки - C++
народ помогите нужны программки для 1)сортировки прямым выбором(по убыванию 5&gt;3&gt;1) 2)сортировка двоичной вставкой(по возрастанию 1&lt;3&lt;5)...

Сортировки? - C++
На экзамене нам дали такое задание &quot;Написать функцию сортировки вектора строк.&quot; Подскажите как можно решить эту программу если мы...


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

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

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