Форум программистов, компьютерный форум CyberForum.ru

Пирамидальная сортировка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
Joker=)
Сообщений: n/a
27.05.2011, 10:10     Пирамидальная сортировка #1
дайте пожалуйста код на сортировку массива пирамидальной сортировкой.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.05.2011, 10:10     Пирамидальная сортировка
Посмотрите здесь:

Пирамидальная сортировка C++
Пирамидальная сортировка C++
пирамидальная сортировка C++
C++ Пирамидальная сортировка
C++ Пирамидальная сортировка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nobless1368
 Аватар для nobless1368
14 / 14 / 1
Регистрация: 04.06.2012
Сообщений: 124
Записей в блоге: 1
25.08.2012, 17:48     Пирамидальная сортировка #2
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
#include <iterator>
 
template< typename Iterator >
void adjust_heap( Iterator first
                  , typename std::iterator_traits< Iterator >::difference_type current
                  , typename std::iterator_traits< Iterator >::difference_type size
                  , typename std::iterator_traits< Iterator >::value_type tmp )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
 
    diff_t top = current, next = 2 * current + 2;
 
    for ( ; next < size; current = next, next = 2 * next + 2 )
    {
        if ( *(first + next) < *(first + next - 1) )
            --next;
        *(first + current) = *(first + next);
    }
 
    if ( next == size )
        *(first + current) = *(first + size - 1), current = size - 1;
 
    for ( next = (current - 1) / 2;
          top > current && *(first + next) < tmp;
          current = next, next = (current - 1) / 2 )
    {
        *(first + current) = *(first + next);
    }
    *(first + current) = tmp;
}
 
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
    typedef typename std::iterator_traits< Iterator >::value_type value_t;
 
    value_t tmp = *--last;
    *last = *first;
    adjust_heap( first, 0, last - first, tmp );
}
 
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
    for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
        adjust_heap( first, current, last - first, *(first + current) );
 
    while ( first < last )
        pop_heap( first, last-- );
}
Extro
0 / 0 / 0
Регистрация: 11.06.2012
Сообщений: 31
13.11.2012, 08:48     Пирамидальная сортировка #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
38
39
40
41
42
43
44
void pyramid(){ 
    int sh = 0; //смещение
    bool b = false;
    while(1){
        b = false;
        for ( int i = 0; i < RazmerMass; i++ ){
            if( i * 2 + 2 + sh < RazmerMass ){
                KolvSravn++;
                if( ( mass[i + sh] > mass[i * 2 + 1 + sh] ) || ( mass[i + sh] >  mass[i * 2 + 2 + sh])){
                    KolvSravn++;
                    if ( mass[i * 2 + 1 + sh] <  mass[i * 2 + 2 + sh] ){
                         KolvPeres++;
                        swap( mass[i + sh], mass[i * 2 + 1 + sh] );
                        b = true;
                    }
                    else {KolvSravn++;
                         if ( mass[i * 2 + 2 + sh] < mass[ i * 2 + 1 + sh]){
                         KolvPeres++;
                             swap( mass[ i + sh], mass[i * 2 + 2 + sh]);
                             b = true;
                         }
                    }    
                }
                KolvSravn++;
                    if( mass[i*2 + 2 + sh] < mass[i*2 + 1 + sh] ){
                        KolvPeres++;
                        swap( mass[i*2+1+sh], mass[i * 2 +2+ sh] );
                        b = true;
                        }
            }
            else if( i * 2 + 1 + sh < RazmerMass ){
                       KolvSravn++;
                     if( mass[i + sh] > mass[ i * 2 + 1 + sh] ){
                         KolvPeres++;
                         swap( mass[i + sh], mass[i * 2 + 1 + sh] );
                         b = true;
                     }
                 }
        }
        if (!b) sh++; 
        
        if ( sh + 2 == RazmerMass ) break; 
    } 
}
где
RazmerMass - количество элементов в массиве,
mass[] - собственно сам массив
KolvSravn - количество сравнений элементво
KolvPeres - количество пересылок элементов
Сортирует нормально. Но, по определению его сложность Θ(n log n) при любых условиях.
На случайном не отсортированном массиве в 200 элементов:
KolvSravn = 32659
KolvPeres = 2917
На том же, но отсортированном массиве:
KolvSravn = 19899
Может, у меня не так стоят счетчики сравнений/пересылок, почему я не могу увидеть сложность 200 * log 200 = 460?
Extro
0 / 0 / 0
Регистрация: 11.06.2012
Сообщений: 31
17.11.2012, 12:28     Пирамидальная сортировка #4
вопрос еще актуален
XlaM
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 2
07.11.2013, 19:44     Пирамидальная сортировка #5
Ап!
Yandex
Объявления
07.11.2013, 19:44     Пирамидальная сортировка
Ответ Создать тему
Опции темы

Текущее время: 14:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru