Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.79
Joker=)
0 / 0 / 0
Регистрация: 23.05.2011
Сообщений: 1
#1

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

27.05.2011, 10:10. Просмотров 3194. Ответов 4
Метки нет (Все метки)

дайте пожалуйста код на сортировку массива пирамидальной сортировкой.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.05.2011, 10:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пирамидальная сортировка (C++):

Сортировка Шелла и пирамидальная сортировка для символов - C++
Здраствуйте, можете пожалуйста привести пример сортировок шелла и пиромидальной сортировки для символов, а то ничего не могу ...

2 сортировки: пирамидальная сортировка и сортировка слиянием - C++
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель качества сортировки (количество операций, т.е....

Пирамидальная сортировка - C++
Здраствуйте! Я хотел бы вас попросить о помощи! Помогите пожалуйста сделать это задание методом пирамидальной сортировки. ...

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

Пирамидальная сортировка - C++
Здравствуйте! Хотела попросить помощи. Мне нужно отсортировать дерево пирамидальной сортировкой. Создание дерева у меня есть, но сортировка...

Пирамидальная сортировка - C++
Может кто может выложить примеры: 1) пирамидальной сортировки 2) сортировка простым выбором Они нужны в курсовую как примеры ...

4
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-- );
}
0
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?
0
Extro
0 / 0 / 0
Регистрация: 11.06.2012
Сообщений: 31
17.11.2012, 12:28 #4
вопрос еще актуален
0
XlaM
0 / 0 / 0
Регистрация: 07.11.2013
Сообщений: 2
07.11.2013, 19:44 #5
Ап!
0
07.11.2013, 19:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 19:44
Привет! Вот еще темы с ответами:

Пирамидальная сортировка - C++
Каким будет порядок элементов списка после применения к нему этапа построения пирамиды? Поделитесь опытом, желанно парочку комментарий...

Пирамидальная сортировка - C++
Здравствуйте, написал пирамидальную сортировку с костылями, которая вроде и работает, но если сдавать, то 10 тестов из 30 проходит, вот...

Пирамидальная сортировка - C++
Добрый Вечер! Нужно сделать Пирамидальную сортировку. Немного получилось, но программа работает так как хотелось бы. Не сортирует...

Пирамидальная сортировка - C++
Всем hello!!! Плиз помогите реализовать пирамидальную сортировку на С++!!! Зарание блогодарен!!!


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.