0 / 0 / 3
Регистрация: 11.12.2016
Сообщений: 137
|
|
|
1
|
является ли это алгоритм сортировкой кучеу(пирамидальный)?
17.10.2017, 10:17. Показов 393. Ответов 0
дамы и господа код который вы видите внизу является ли сортировкой кучей? это глупый вопрос из того что припод это отрицает. исходный код получен из сайта: ->суда<-
| 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
| #include <iostream>
void iswap (int &n1, int &n2) {
int temp = n1;
n1 = n2;
n2 = temp;
}
int main () {
unsigned const n = 100u;
int a[n];
// Для наглядности заполняем массив числами от n до 0.
for (unsigned i = 0u; i < n; ++i) {
a[i] = n - i;
std::cout << a[i] << ' ';
}
// ----------- Сортировка ------------
// Сортирует по возрастанию. Чтобы получить сортировку по убыванию,
// поменяйте знаки сравнения в строчках, помеченных /*(знак)*/
unsigned sh = 0u; // Смещение
bool b;
do {
b = false;
for (unsigned i = 0u; i < n; ++i) {
if (i * 2 + 2 + sh < n) {
if ((a[i + sh] > /*<*/ a[i * 2 + 1 + sh]) || (a[i + sh] > /*<*/ a[i * 2 + 2 + sh])) {
if (a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
} else if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 2 + sh]);
b = true;
}
}
// Дополнительная проверка для последних двух элементов;
// с её помощью можно отсортировать пирамиду
// состоящую всего лишь из трёх элементов
if (a[i * 2 + 2 + sh] < /*>*/ a[i * 2 + 1 + sh]) {
iswap(a[i * 2 + 1 + sh], a[i * 2 + 2 + sh]);
b = true;
}
} else if (i * 2 + 1 + sh < n) {
if (a[i + sh] > /*<*/ a[ i * 2 + 1 + sh]) {
iswap(a[i + sh], a[i * 2 + 1 + sh]);
b = true;
}
}
}
if (!b)
++sh; // Смещение увеличивается, когда на текущем этапе сортировать больше нечего
} while (sh + 2 < n); // Конец сортировки
std::cout << std::endl << std::endl;
for (unsigned i = 0u; i < n; ++i)
std::cout << a[i] << ' ';
return 0;
} |
|
Кликните здесь для просмотра всего текста
после от редактирования мной | 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
| // lab2_primidalni.cpp: определяет точку входа для консольного приложения.O(n*logn)
//n-1
#include "stdafx.h"
#include <iostream>
#include <locale.h>
#include <ctime>
using namespace std;
void iswap(int &n1, int &n2) {
int temp = n1;
n1 = n2;
n2 = temp;
}
void pyramidsort(int *a, int n) {
int k = 0;
bool f;
do {
f = false;
for (int i = 0; i < n; i++) {
if (i * 2 + 2 + k < n) {
if (a[i + k] > a[i * 2 + 1 + k] || a[i + k] > a[i * 2 + 2 + k]) {
if (a[i * 2 + 1 + k] < a[i * 2 + 2 + k]) {
iswap(a[i + k], a[i * 2 + 1 + k]);
f = true;
}
else if (a[i * 2 + 2 + k] < a[i * 2 + 1 + k]) {
iswap(a[i + k], a[i * 2 + 2 + k]);
f = true;
}
}
if (a[i * 2 + 2 + k] < a[i * 2 + 1 + k]) {
iswap(a[i * 2 + 1 + k], a[i * 2 + 2 + k]);
f = true;
}
}
else if (i * 2 + 1 + k < n) {
if (a[i + k] > a[i * 2 + 1 + k]) {
iswap(a[i + k], a[i * 2 + 1 + k]);
f = true;
}
}
}
if(!f)
k++;
} while (k + 2 < n);
}
int main() {
setlocale(LC_ALL, "Rus");
srand(time(0));
unsigned int start_time, end_time;
int n, ques;
char q;
char yes = 'y';
cout << "Вводите размер массива: ";
cin >> n;
int *a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = rand() % 100 - 50;
}
cout << "Вводить созданная массив на экран: (y or n) ";
cin >> q;
switch (q == yes) {
case 1:for (int i = 0; i < n;i++) {
cout << a[i] << " ";
}
break;
}
cout << endl;
cout << "Резултат:\n";
start_time = clock();
pyramidsort(a, n);
end_time = clock();
if (q == yes)
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << "runtime = " << (end_time - start_time) / (CLOCKS_PER_SEC/1000.0) << endl; // время работы программы
return 0;
} |
|
0
|
(
