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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 26.12.2009, 21:20
Новичок

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

Инварианты пирамидальной сортировки.
У меня есть такая реализация этого замечательного алгоритма(написанная на С по псевдокоду из книги Кормена и Ко "Алгоритмы: построение и анализ"):

void downHeap(int a[], int k, int n)
{
int l = 2*k + 1;
int r = 2*k + 2;
int largest = 0;
int tmp = 0;

if (l <= n && a[l] > a[k])
largest = l;
else
largest = k;

if (r <= n && a[r] > a[largest])
largest = r;

if (largest != k)
{
tmp = a[k];
a[k] = a[largest];
a[largest] = tmp;
downHeap(a, largest, n);
}
}

void heapSort(int a[], int size)
{
int i;
int temp;

for(i=size/2-1; i >= 0; i--)
downHeap(a, i, size-1);

for (i = size - 1; i > 0; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;

downHeap(a, 0, i-1);
}
}

Может кто-нибудь подсказать, как расписать инварианты и постусловия для такой реализации(постусловия для функций, инварианты и постусловия - для циклов).

У меня есть своя версия(правда не полная пока что), однако хотелось бы посоветоваться с коллегами =)
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Эффективность алгоритмов сортировки Andrey K Сортировка и поиск 10 12.12.2009 18:50
Сортировки гость Сортировка и поиск 2 28.11.2009 07:34
Анализ алгоритма сортировки. _asm Сортировка и поиск 21 20.06.2008 19:57
Помогите запрограмировать шаг для сортировки 2^p*3^q petr pupkin Сортировка и поиск 4 28.05.2008 19:28
помогите решить (код поразрядной сортировки) незарегистрированный Реализация, исходники, языки 5 01.06.2007 13:16