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

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

03.03.2015, 23:19. Показов 5132. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.03.2015, 23:19
Ответы с готовыми решениями:

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

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

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

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

3
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
05.03.2015, 09:41  [ТС] 2
Неужели никто не сможет помочь?
0
Эксперт по математике/физикеЭксперт С++
2001 / 1332 / 379
Регистрация: 16.05.2013
Сообщений: 3,450
Записей в блоге: 6
05.03.2015, 10:31 3
Цитата Сообщение от SLICK_2011 Посмотреть сообщение
Неужели никто не сможет помочь?
А тут нечего помогать ибо количество операций зависит от структуры данных. То что результаты у вас не укладываются в теоретические это не удивительно. Теоретическая сложность дает лишь качественные оценки, а не количественные и поэтому проводить подобные сравнения некорректно.
0
0 / 0 / 0
Регистрация: 03.03.2015
Сообщений: 4
05.03.2015, 18:09  [ТС] 4
Вы меня не поняли. Я понимаю, что теоретическая оценка не будет совпадать с экспериментальной, и оцениваю я как раз не количество. Как я понял, вы под структурой данных понимаете экземпляр типа данных, который во всех случаях постоянный. Из этого следует, что соотношение между экспериментальной и теоретической оценкой (для 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.03.2015, 18:09
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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