Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.08.2010, 00:54
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Возможная неточность в пирамидальной сортировке
В статье "Пирамидальная сортировка" допущена неточность:
В функции "void downHeap( int *a, long k, long n )", при передаче нечетного n, внутри главного цикла происходит обращение к элементу массива номер n, то есть лежащему за границей массива.
Предположем, что n = N * 2 + 1, тогда k = N, child = N * 2, то есть child < n и, следовательно, произойдет сравнение child[ N * 2 ] и child[ N * 2 + 1 ].

Исправить можно
Код:
        if( child + 1 < n && a[ child ] < a[ child + 1 ] )
            child++;
но нужно ли? Вопрос в том се баг или фича?

http://algolist.ru/sort/pyramid_sort.php
  #2  
Старый 02.08.2010, 01:24
гость

 
Сообщений: n/a

да там вообще какой-то бред написан и все перепутано

в тексте статьи говорится о нумерации массива с нуля (соответсвенно дети i-й вершины будут 2i+1 и 2i+2), а в этом коде - нумерация с единицы (соотв. дети: 2i и 2i+1).
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Ошибка в коде к статье по сортировке слиянием. Семён[гость] Замечания о работе сайта 0 23.05.2010 18:55
Задача о сортировке пузырьком Fredo Сортировка и поиск 4 29.04.2010 22:02
Алгоритм пирамидальной сортировки sasha198407 Сортировка и поиск 0 27.01.2010 23:31
Инварианты пирамидальной сортировки. Timmy Сортировка и поиск 0 26.12.2009 21:20
вопрос по сортировке Wind Of Change Сортировка и поиск 3 18.05.2008 16:41