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

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

11.11.2019, 14:47. Показов 1553. Ответов 6

необходимо поставить гдето счетчики на проверку количества сравнений и обменов сделанных сортировкой
не получается .
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap, counter_forif++) надо как то эту запись разрулить


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int shellSort(int arr[], int n, long long& counter_forif,long long& counter_ob)
{
for (int gap = n / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < n; i += 1)
{
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap, counter_forif++)
arr[j] = arr[j - gap];
//counter_forif++;
arr[j] = temp;
counter_ob++;
}
}
return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.11.2019, 14:47
Ответы с готовыми решениями:

Отсортировать 5 массивов пирамидальной сортировкой и подсчитать количество сравнений и обменов
Отсортировать массивы h1,h2,h3,h4,h5 с помощью пирамидальной сортировки и подсчитать количество...

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

Сортировке Шейкера (подсчет количества сравнений и обменов)
Здравствуйте, пожалуйста, помогите исправить ошибку в сортировке Шейкера (подсчет количества...

Счетчики количества перестановок и сравнений Шейкерной сортировки
Помогите ввести счетчики перестановок и сравнений Закоментированный код по идее верен но c ним...

6
7424 / 5019 / 2890
Регистрация: 18.12.2017
Сообщений: 15,694
11.11.2019, 14:52 2
Лучший ответ Сообщение было отмечено ARTHURPRO как решение

Решение

возможно подойдёт такой вариант, счётчики добавляйте сами
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Shell_sort(int *a, int n)
{
   int step=n/2;
    while (step > 0)
    {
      for (int i = 0; i < n-step; i++)
            {
                 int j=i;
                 while (j >= 0 && a[j] >a[j+step])
                    {
                        int temp=a[j];
                        a[j]=a[j+step];
                        a[j+step]=temp;
                        j--; 
                    }
                }
           step=step/2;
        }
}
1
0 / 0 / 0
Регистрация: 31.10.2019
Сообщений: 21
11.11.2019, 14:55  [ТС] 3
вроде правильно счетчики поставил
но боюсь ваша сорта за квадрат будет работать

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Shell_sort(int *a, int n)
{
   int step=n/2;
    while (step > 0)
    {
      for (int i = 0; i < n-step; i++)
            {
 
// счетчик ифов
                 int j=i;
                 while (j >= 0 && a[j] >a[j+step])
                    {
                        int temp=a[j];
                        a[j]=a[j+step];
                        a[j+step]=temp;
                        j--; 
// счетчик обменов 
                    }
                }
           step=step/2;
        }
0
7424 / 5019 / 2890
Регистрация: 18.12.2017
Сообщений: 15,694
11.11.2019, 15:05 4
Цитата Сообщение от ARTHURPRO Посмотреть сообщение
вроде правильно счетчики поставил
насчёт счётчика обменов согласен, а в чём смысл
Цитата Сообщение от ARTHURPRO Посмотреть сообщение
// счетчик ифов
там результат n-step-1
0
0 / 0 / 0
Регистрация: 31.10.2019
Сообщений: 21
11.11.2019, 15:11  [ТС] 5
то есть результат n-step-1 зависит от 2 переменных всегда ? я правильно понял? и почему -1?)
Спасибо вам огромное
0
7424 / 5019 / 2890
Регистрация: 18.12.2017
Сообщений: 15,694
11.11.2019, 15:20 6
ARTHURPRO, я не учёл, что там внешний цикл ещё, наверное правильно у Вас.
0
0 / 0 / 0
Регистрация: 31.10.2019
Сообщений: 21
11.11.2019, 15:35  [ТС] 7
Алгоритм всегда будет иметь одинаковое количество сравнений (N2 -1) и перестановок (N – 1).
(где N – кол-во ячеек в массиве).
нашел на форуме
что скажете?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.11.2019, 15:35
Помогаю со студенческими работами здесь

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

Подсчет количества сравнений и обменов в процессе упорядочения методом Хоара
Есть сортировка методом Хоара, нужно еще сделать подсчет количества сравнений и обменов в процессе...

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

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


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

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

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