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

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

13.06.2019, 11:35. Показов 280. Ответов 0

Author24 — интернет-сервис помощи студентам
Не работает сортировка Heap sort с использованием итераторов(обобщенный алгоритм). Она сортирует элементы корректно раз в несколько запусков, в остальных случаях, если брать,например, 5 элементов, то корректно отсортирует 2,3, 4 элементы, а 1 и 5 перепутает местами. Не понимаю, где ошибка в коде.
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
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 <class Iterator>
void pop_heapp( 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 <class Iterator>
void heapSort3( 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_heapp( first, last-- );
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2019, 11:35
Ответы с готовыми решениями:

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

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

Проблема с сортировкой строк
Вот собственно кусок кода, необходимо отсортировать значения строк в классе. Проблема в том что...

Отсортировать одномерный массив, заполненный случайными числами, сортировкой Шелла и сортировкой выбором
Отсортировать одномерный массив, заполненный случайными числами, сортировкой Шелла и сортировкой...

0
13.06.2019, 11:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.06.2019, 11:35
Помогаю со студенческими работами здесь

Упорядочивание быстрой/пирамидальной сортировкой по выбору пользователя
Ребят,всем привет!Требуется срочно ваша помощь!Помогите написать программу,которая будет...

Проблема со случайной сортировкой
Всем привет. Столкнулся с непонятной для меня проблемой. Есть запрос: SELECT * FROM a WHERE akey...

Проблема с сортировкой в Excel
:( Я уже поднимал тему на счет того, что если вводить в Excel строку '123e7', то оно заменяет его...

Проблема с сортировкой CheckBox в DataGridView
Дорогие гуру, у меня такая проблема: Есть DataGridView, в нем одна из колонок типа CheckBox....


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

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

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