0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4

Количество обменов и сравнений в HeapSort

03.03.2015, 23:19. Показов 5955. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем доброго времени суток! Помогите, пожалуйста, разобраться с задачей. Мне нужно подсчитать количество обменов и сравнений в пирамидальной сортировке. Нашел программу (возможно даже здесь, не помню, ее код будет ниже), которая производит сортировку и подсчитывает данные значения. Сортирую я массив элементов типа int, который заполняется случайным образом. Для тестирования я брал размерность 100, 500, 1000 и 5000. Результаты работы программы в прикрепленных файлах.

Для удобства отображу это так :

Размерность К-сто сравнений К-ство обменов
100----------------34040---------------------924
500----------------857254--------------------23351
1000----------------3429339------------------86187
5000----------------85004946-----------------1989531

Насколько я понял (возможно неправильно ), посчитать теоретическую оценку для этих значений (сравнений и обменов), я могу по формуле n*logn. Я знаю что она будет достаточно сильно отличаться от значений в программе, но соотношение К-ство сравнений(в программе) / К-ство сравнений(в теории) и К-ство обменов(в программе) / К-ство обменов(в теории) должно быть относительно постоянным (допускается вроде +/- 10%) независимо от размерности массива. У меня же выходит это соотношение для разных размерностей отличается на порядки:


100: 100*log100 = 200; 924/200=4.62; 34040/200=170.2
500: 500*log500 = 1349.49; 23351/1349.49 = 66.8; 857254/1349.49 = 635.24
Ну вообщем и так далее.

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

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
#include <iostream>
#include <conio.h>
#include <windows.h>
#include <ctime>
 
using namespace std;
void iswap(int &n1, int &n2)//обмен
{     
    int temp = n1;
    n1 = n2;
    n2 = temp;
}
 int main(){
    
    FILE *f1,*f2;
    setlocale(0,"");
    srand(time(NULL));  
    puts("Пирамидальная сортировка:\n");{
    int countcompare=0; //счетчик сравнений
    int countswap=0; //счетчик обменов
    int const n = 500;
    int a[n];
    f1=fopen("F:\\before_HeapSort.txt","w");
    fprintf(f1,"Start array [length = %d]: ",n);
    for ( int i = 0; i < n; ++i ) 
    {
        a[i]=rand();
        fprintf(f1,"%d ",a[i]);
    }
    fclose(f1);
 
    for ( int i = 0; i < n; ++i ) 
    cout<<a[i]<<" ";
    
    //-----------сортировка------------//
    
    int sh = 0; //смещение
    bool b = false;
    for(;;)
    {
    b = false;
    for ( int i = 0; i < n; i++ )
    {  
        if( countcompare++,i * 2 + 2 + sh < n )
        {
        if(countcompare++, ( a[i + sh] > /*<*/ a[i * 2 + 1 + sh] ) || ( a[i + sh] > /*<*/ a[i * 2 + 2 + sh] ) )
        {
            if (countcompare++, a[i * 2 + 1 + sh] < /*>*/ a[i * 2 + 2 + sh] )
            {
            iswap( a[i + sh], a[i * 2 + 1 + sh] );countswap++;
            b = true;
            }
            else if (countcompare++, a[i * 2 + 2 + sh] < /*>*/ a[ i * 2 + 1 + sh])
                 {
                     iswap( a[ i + sh], a[i * 2 + 2 + sh]);countswap++;
                     b = true;
                 }
        }
        //дополнительная проверка для последних двух элементов
               
            if( countcompare++,a[i*2 + 2 + sh] < /*>*/ a[i*2 + 1 + sh] )
            {
            iswap( a[i*2+1+sh], a[i * 2 +2+ sh] );countswap++;
                        b = true;
            }
        }
        else if( countcompare++,i * 2 + 1 + sh < n )
             {
                 if( countcompare++,a[i + sh] > /*<*/ a[ i * 2 + 1 + sh] )
                 {
                     iswap( a[i + sh], a[i * 2 + 1 + sh] );countswap++;
                     b = true;
                 }
             }
    }
    if (!b) sh++; //смещение увеличивается, когда на текущем этапе
              //сортировать больше нечего
    if ( sh + 2 == n ) break;
    }  //конец сортировки
 
 
    
    puts("\n\nПосле сортировки:\n");
    f2=fopen("F:\\after_HeapSort.txt","w");
    fprintf(f2,"Сравнений: %d\n",countcompare);
    fprintf(f2,"Обменов: %d\n",countswap);
    fprintf(f2,"Sort array [length = %d]: ",n);
    for ( int i = 0; i < n; ++i ) 
    {
        cout << a[i] << " ";
        fprintf(f2,"%d ",a[i]);         
    }
    cout << endl << endl;
    cout<<"\nРазмерность: "<<n;
    cout<<"\nСравнений:"<<countcompare;
    cout<<"\nОбменов"<<countswap<<endl;
    fclose(f2);
    
    
    }
    
    getch();
    return 0;
}
Миниатюры
Количество обменов и сравнений в HeapSort   Количество обменов и сравнений в HeapSort   Количество обменов и сравнений в HeapSort  

Количество обменов и сравнений в HeapSort  
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
03.03.2015, 23:19
Ответы с готовыми решениями:

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

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

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

3
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
05.03.2015, 09:41  [ТС]
Неужели никто не сможет помочь?
0
Эксперт по математике/физикеЭксперт С++
 Аватар для Ilot
2217 / 1420 / 414
Регистрация: 16.05.2013
Сообщений: 3,612
Записей в блоге: 6
05.03.2015, 10:31
Цитата Сообщение от SLICK_2011 Посмотреть сообщение
Неужели никто не сможет помочь?
А тут нечего помогать ибо количество операций зависит от структуры данных. То что результаты у вас не укладываются в теоретические это не удивительно. Теоретическая сложность дает лишь качественные оценки, а не количественные и поэтому проводить подобные сравнения некорректно.
0
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
05.03.2015, 18:09  [ТС]
Вы меня не поняли. Я понимаю, что теоретическая оценка не будет совпадать с экспериментальной, и оцениваю я как раз не количество. Как я понял, вы под структурой данных понимаете экземпляр типа данных, который во всех случаях постоянный. Из этого следует, что соотношение между экспериментальной и теоретической оценкой (для n =500, 1000, ...) должно быть относительно постоянным.
Кликните здесь для просмотра всего текста
Если взять данные приведенные в этом исследовании, можно убедиться, что там это пропорция соблюдается:
43/10 = 4.3 (n=10)
823/200 = 4.115 (n=100)
5274/1350 = 3.9 (n=500)
11538/3000 = 3.9 (n=1000)
То есть то, о чем я говорил, все-таки имеет место. В программе, код которой я скинул выше, это выглядит следующим образом: при переходе с n=100 к n=500 отношение меняется с 4.62 до 66.8 (то есть в 14.5 раз увеличивается, и это так и продолжается с увеличением размерности без всякой закономерности), а не на 0.1-0.6 как по идее для этого случая должно быть.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
05.03.2015, 18:09
Помогаю со студенческими работами здесь

Как теоретически (не программно) посчитать количество сравнений и обменов в пузырьковой сортировке?
как теоретически посчитать количество сравнений и обменов в пузырьковой сортировке?не программно

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

Поставить счетчики на проверку количества сравнений и обменов сделанных сортировкой
необходимо поставить гдето счетчики на проверку количества сравнений и обменов сделанных сортировкой не получается . for (j = i; j...

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

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


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

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

Новые блоги и статьи
Реализация Domain-Driven Design с Java
Javaican 20.05.2025
DDD — это настоящий спасательный круг для проектов со сложной бизнес-логикой. Подход, предложенный Эриком Эвансом, позволяет создавать элегантные решения, которые точно отражают реальную предметную. . .
Возможности и нововведения C# 14
stackOverflow 20.05.2025
Выход версии C# 14, который ожидается вместе с . NET 10, приносит ряд интересных нововведений, действительно упрощающих жизнь разработчиков. Вы уже хотите опробовать эти новшества? Не проблема! Просто. . .
Собеседование по Node.js - вопросы и ответы
Reangularity 20.05.2025
Каждому разработчику рано или поздно приходится сталкиватся с техническими собеседованиями - этим стрессовым испытанием, где решается судьба карьерного роста и зарплатных ожиданий. В этой статье я. . .
Cython и C (СИ) расширения Python для максимальной производительности
py-thonny 20.05.2025
Python невероятно дружелюбен к начинающим и одновременно мощный для профи. Но стоит лишь заикнуться о высокопроизводительных вычислениях — и энтузиазм быстро улетучивается. Да, Питон медлительнее. . .
Безопасное программирование в Java и предотвращение уязвимостей (SQL-инъекции, XSS и др.)
Javaican 19.05.2025
Самые распространёные векторы атак на Java-приложения за последний год выглядят как классический "топ-3 хакерских фаворитов": SQL-инъекции (31%), межсайтовый скриптинг или XSS (28%) и CSRF-атаки. . .
Введение в Q# - язык квантовых вычислений от Microsoft
EggHead 19.05.2025
Microsoft вошла в гонку технологических гигантов с собственным языком программирования Q#, специально созданным для разработки квантовых алгоритмов. Но прежде чем погружаться в синтаксические дебри. . .
Безопасность Kubernetes с Falco и обнаружение вторжений
Mr. Docker 18.05.2025
Переход организаций к микросервисной архитектуре и контейнерным технологиям сопровождается лавинообразным ростом векторов атак — от тривиальных попыток взлома до многоступенчатых кибератак, способных. . .
Аугментация изображений с Python
AI_Generated 18.05.2025
Собрать достаточно большой датасет для обучения нейронной сети — та ещё головная боль. Часами вручную размечать картинки, скармливать их ненасытным алгоритмам и молиться, чтобы модель не сдулась при. . .
Исключения в Java: советы, примеры кода и многое другое
Javaican 18.05.2025
Исключения — это объекты, созданные когда программа сталкивается с непредвиденной ситуацией: файл не найден, сетевое соединение разорвано, деление на ноль. . . Список можно продолжать до бесконечности. . . .
Как сделать SSO (Single Sign-On) в C# приложении
stackOverflow 18.05.2025
SSO — это механизм, позволяющий пользователю пройти аутентификацию один раз и получить доступ к нескольким приложениям без повторного ввода учетных данных. Вы наверняка сталкивались с ним, когда. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru