0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
1

Отсортировать 5 массивов пирамидальной сортировкой и подсчитать количество сравнений и обменов

01.03.2020, 21:01. Показов 3057. Ответов 27
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Отсортировать массивы h1,h2,h3,h4,h5 с помощью пирамидальной сортировки и подсчитать количество сравнений и обменов для
среднего, наилучшего и наихудшего случая(массив случайных чисел, массив уже отсортирован, массив отсортирован в обратном порядке).

Не могу понять куда поставить счетчики сравнений и обменов чтобы вывести их на экран.
Вот сам код.
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
#include <iostream>
#include <cmath>
 
using namespace std;
//создаем кучу
void heap(int* a, int i, int n) {
    int max = i;
    while (true) {
        int child = 2 * i + 1;
        if (child < n && a[child] > a[max]) {
            max = child;
        }
        child++;
        if (child < n && a[child] >a [max]) {
            max = child;
        }
        if ( max == i) {
            break;
        }
        else {
            swap(a[max], a[i]);
            i = max;
        }
    }
}
// сама сортировка
void heapsort(int* a, int n) {
    int i;
    for (i = n / 2; i >= 0; i--) {
        int max = i;
        heap(a, i, n);
    }
    for (i = n - 1; i >= 1; i--) {
        swap(a[0], a[i]);
        heap(a, 0, i);
    }
    
}  
 
 
 
void invertSort1(int* m, int ln) {
    int i, j, key;
    for (j = 1; j < ln; j++) {
        key = m[j];
        i = j - 1;
        while (i >= 0 && m[i] < key) {
            m[i + 1] = m[i];
            i--;
        }
        m[i + 1] = key;
    }
}
 
int main() {
    setlocale(LC_ALL, "rus");
    int i = 0, h1[30000], h2[40000], h3[50000], h4[60000], h5[70000];
 
    for (i = 0; i < 30000; i++) {
        h1[i] = rand();
    }
    for (i = 0; i < 40000; i++) {
        h2[i] = rand();
    }
    for (i = 0; i < 50000; i++) {
        h3[i] = rand();
    }
    for (i = 0; i < 60000; i++) {
        h4[i] = rand();
    }
    for (i = 0; i < 70000; i++) {
        h5[i] = rand();
    }
 
    cout << "Контрольны прогоны программы для алгоритма пирамидальной сортировки." << endl;
    cout << "_________________________\nn1 = 30 000\nСредний случай\n";
    heapsort(h1, 30000);
 
    cout << "Наилучший случай\n";
    heapsort(h1, 30000);
 
    cout << "Наихудший случай\n";
    invertSort1(h1, 30000);
    heapsort(h1, 30000);
 
    cout << "_________________________\nn2 = 40 000\nСредний случай\n";
    heapsort(h2, 40000);
 
    cout << "Наилучший случай\n";
    heapsort(h2, 40000);
 
    cout << "Наихудший случай\n";
    invertSort1(h2, 40000);
    heapsort(h2, 40000);
 
    cout << "_________________________\nn3 = 50 000\nСредний случай\n";
    heapsort(h3, 50000);
 
    cout << "Наилучший случай\n";
    heapsort(h3, 50000);
 
    cout << "Наихудший случай\n";
    invertSort1(h3, 50000);
    heapsort(h3, 50000);
 
    cout << "_________________________\nn4 = 60 000\nСредний случай\n";
    heapsort(h4, 60000);
 
    cout << "Наилучший случай\n";
    heapsort(h4, 60000);
 
    cout << "Наихудший случай\n";
    invertSort1(h4, 60000);
    heapsort(h4, 60000);
 
    cout << "_________________________\nn5 = 70 000\nСредний случай\n";
    heapsort(h5, 70000);
 
    cout << "Наилучший случай\n";
    heapsort(h5, 70000);
 
    cout << "Наихудший случай\n";
    invertSort1(h5, 70000);
    heapsort(h5, 70000);
    return 0;
}
Добавлено через 46 минут
Никто не поможет?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.03.2020, 21:01
Ответы с готовыми решениями:

Поставить счетчики на проверку количества сравнений и обменов сделанных сортировкой
необходимо поставить гдето счетчики на проверку количества сравнений и обменов сделанных...

Отсортировать одномерный массив по возрастанию пирамидальной сортировкой
Пожалуйста, помогите найти ошибку. Нужно отсортировать одномерный массив по возрастанию...

Подсчитать количество сравнений исходного и отсортированного массивов
Доброго времени суток. Нужна помощь в подсчете количества сравнений.Вот код uses crt; const N =...

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

27
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 09:46 2
Цитата Сообщение от Astreemonter Посмотреть сообщение
Не могу понять куда поставить счетчики сравнений и обменов чтобы вывести их на экран.
Там где сравниваешь a[...], например a[child] >a [max] - увеличивай счётчик сравнений.
Там, где делашь для него swap - swap(a[max], a[i]) - там счётчик перестановок
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 19:36  [ТС] 3
Я вроде бы сделал как вы сказали но он выводит С и М равные нулю


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
void heap(int* a, int i, int n) {
    unsigned long long int C = 0, M = 0;
    int max = i;
    while (true) {
        int child = 2 * i + 1;
        if (C++, child < n && a[child] > a[max]) {
            max = child;
        }
        child++;
        if (C++, child < n && a[child] >a[max]) {
            max = child;
        }
        if (C++, max == i) {
            break;
        }
        else {
            swap(a[max], a[i]);
            i = max;
            M++;
        }
    }
 
}
// сама сортировка
void heapsort(int* a, int n) {
    unsigned long long int C = 0, M = 0;
    int i;
    for (i = n / 2; i >= 0; i--) {
        int max = i;
        heap(a, i, n);
    }
    for (i = n - 1; i >= 1; i--) {
        swap(a[0], a[i]);
        heap(a, 0, i);
    }
    cout << "C = " << C  << " M = " << M << endl;
}
Миниатюры
Отсортировать 5 массивов пирамидальной сортировкой и подсчитать количество сравнений и обменов  
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 20:35 4
Лучший ответ Сообщение было отмечено Astreemonter как решение

Решение

Цитата Сообщение от Astreemonter Посмотреть сообщение
Я вроде бы сделал как вы сказали но он выводит С и М равные нулю
Зачем ты C++ внёс внутрь if()?
Цитата Сообщение от Astreemonter Посмотреть сообщение
if (C++, child < n && a[child] > a[max]) {
C++
1
2
C++;
if (child < n && a[child] > a[max])
Добавлено через 3 минуты
Ну и не забывай, что С надо увеличивать, только когда ты сравниваешь a[.......] с чем-нибудь
C++
1
2
3
4
5
6
if (child < n)
{ 
    ++C;
    if (a[child] > a[max])
        max = child;
}
1
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 21:07  [ТС] 5
Так?
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
//создаем кучу
void heap(int* a, int i, int n, unsigned long int &outC, unsigned long int &outM) {
    int max = i;
    while (true) {
        int child = 2 * i + 1;
        if (child < n){
            outC++;
            if (a[child] > a[max])
                max = child;
        }
        child++;
        if (child < n){
            outC++;
            if (a[child] > a[max])
                max = child;
        }
        if ( max == i) {
            break;
        }
        else {
            outM++;
            swap(a[max], a[i]);
            i = max;
        }
    }
 
}
// сама сортировка
void heapsort(int* a, int n) {
    unsigned long int C=0, M=0,b=0, c=0;
    int i;
    for (i = n / 2; i >= 0; i--) {
        int max = i;
        heap(a, i, n,C,M);
    
    }
    for (i = n - 1; i >= 1; i--) {
        M++;
        swap(a[0], a[i]);
        heap(a, 0, i,C,M);
    }
    cout << "C = " << C  << " M = " << M << endl;
}
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 21:20 6
Цитата Сообщение от Astreemonter Посмотреть сообщение
Так?
Ну, вроде похоже. Работает?
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 21:28  [ТС] 7
да, но я не знаю как проверить правильно ли она считает

вот что она выводит
Миниатюры
Отсортировать 5 массивов пирамидальной сортировкой и подсчитать количество сравнений и обменов  
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 21:31 8
Цитата Сообщение от Astreemonter Посмотреть сообщение
да, но я не знаю как проверить правильно ли она считает
Похоже на то. Проверь на массиве из 10 элементов, сравни со сложностью алгоритма.
1
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 21:44  [ТС] 9
я ведь правильно понимаю, что сложность алгоритма n*log(n)?
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 21:51 10
Цитата Сообщение от Astreemonter Посмотреть сообщение
я ведь правильно понимаю, что сложность алгоритма n*log(n)?
Судя по википедии, да. У тебя вроде что-то похожее и получилось.
1
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 22:01  [ТС] 11
Спасибо за помощь.
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 22:03 12
Цитата Сообщение от Astreemonter Посмотреть сообщение
Спасибо за помощь.
Кстати, ты там наилучший и наихудший случаи не перепутал?
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 22:06  [ТС] 13
вроде бы нет
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 22:10 14
Цитата Сообщение от Astreemonter Посмотреть сообщение
нет
Ну ладно. Просто там, на скриншоте, в наилучшем случае сравнений и перестановок больше, чем в наихудшем. Я думал, что должно быть наоборот.
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 22:26  [ТС] 15
еще один вопрос
Как сделать так чтобы был подсчет времени выполнения сортировки для каждого n?
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 22:29 16
Цитата Сообщение от Astreemonter Посмотреть сообщение
Как сделать так чтобы был подсчет времени выполнения сортировки для каждого n?
Что значит "для каждого n" - для каждого вызова heap()?
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
02.03.2020, 22:31  [ТС] 17
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
для каждого вызова heap()?
Ну да
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
02.03.2020, 22:37 18
Цитата Сообщение от Astreemonter Посмотреть сообщение
Ну да
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::chrono::microseconds heap(int* a, int i, int n, unsigned long int& outC, unsigned long int& outM)
{
    const auto tm = std::chrono::steady_clock::now();
    ......................
    return std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - tm);
}
 
..............
 
for (i = n / 2; i >= 0; i--) 
{
    int max = i;
    const auto dt = heap(a, i, n,C,M);
    std::cout << dt.count() << std::endl;
}
0
0 / 0 / 0
Регистрация: 10.12.2019
Сообщений: 69
04.03.2020, 19:29  [ТС] 19
Простите я не правильно сказал у меня вызывается heapsort() и надо подсчитать время которое уйдет на ее выполнение включая то время за которое выполняется функция heap()

Добавлено через 9 минут
Там heap() в цикле for с каждым новым i выполняется heap() и каждый раз время будет другое
мне надо это время сложить и вывести общее время работы

Добавлено через 56 минут
Поможете?
0
6579 / 4564 / 1843
Регистрация: 07.05.2019
Сообщений: 13,726
04.03.2020, 20:51 20
Цитата Сообщение от Astreemonter Посмотреть сообщение
Там heap() в цикле for с каждым новым i выполняется heap() и каждый раз время будет другое
мне надо это время сложить и вывести общее время работы
C++
1
2
3
4
5
6
7
std::chrono::microseconds dt{0};
for (i = n / 2; i >= 0; i--) 
{
    int max = i;
    dt += heap(a, i, n,C,M);
}
std::cout << dt.count() << std::endl;
0
04.03.2020, 20:51
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.03.2020, 20:51
Помогаю со студенческими работами здесь

Сортировка вставками: количество сравнений и обменов
реализация сортировки вставками где поставить счетчики сравнения и обменов ? вот код: //...

Быстрая сортировка: посчитать количество сравнений и обменов
помогите, пожалуйста ) нужно посчитать количество сравнений и обменов в алгоритме &quot;быстрой&quot;...

Для челночной сортировки определить количество сравнений и обменов
Челночная сортировка. Размерность сортируемого массива: n = 10, n = 50, n = 250. Для...

Как посчитать количество обменов и сравнений при сортировке слиянием?
Дан массив: 33 66 82 85 15 17 74 слияние происходит насколько я погимаю так: 66 33 85 82 17 15 74...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru