VPF::[VC++ 2005] пирамидальная сортировка

Jolia

Дата 19.5.2008, 18:30 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 59
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

Здравствуйте все!Помогите пожалуйста разобраться с пирамидальной сортировкой: код я раздобыла а вот понять его никак не получается, не могли бы вы помочь комментариями?) И еще осуществить пошаговый вывод промежуточных результатов. Очень надеюсь на вашу помощь! Всем заранее спасибо за внимание!

Код


#include<iostream>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;


void HeapSort(int *array,int size)
 {
 register int 
i,j,l=size/2,r=size-1;
 int jj=1;
 int temp,sravn;
 int prisv=0;
 sravn=0;
 while(1)
 {
                  

     if(l>0)     
{
      l--;
     temp=array[l];
                 prisv++;
}
      else
{
      temp=array[r];      
                 prisv++; 
     array[r]=array[0];
     prisv++;
      r--; 
      if(r==0)     
           {
          array[0]=temp;
          prisv++;
          return;
      }
     
}
i = l;         
  //array[i]>=array[2i+1],array[i]>=[2i+2] для индексов массива,
 //начинающихся с 0
     while(1)
     {
         j=i;
         i=i*2+1;
         if(i<r) 
         {
            sravn++;
            if(array[i]<array[i+1]) 
                i++;
         }
         else 
            if(i!=r) 
               break;

         sravn++;
         if(temp>=array[i]) 
          break;

         array[j]=array[i]; 
         prisv++;
     }
     array[j] = temp;     
     prisv++;

      jj++;
    }
 }  


void HeapSort1(int *array,int size)
 {
 register int 
i,j,l=size/2,r=size-1;
 int jj=1;
 int temp,sravn;
 int prisv=0;
 sravn=0;
 while(1)
 {
                  

     if(l>0)     
{
      l--;
     temp=array[l];
prisv++;
}
      else
{
      temp=array[r];    
      prisv++; 
     array[r]=array[0];
     prisv++;
         
      r--; 
      if(r==0)     
        
      {
          array[0]=temp;
          prisv++;
          return;
      }
     
}
i = l;     
     
 
 //array[i]>=array[2i+1],array[i]>=[2i+2] для индексов массива,
 //начинающихся с 0
     while(1)
     {
         j=i;
         i=i*2+1;
         if(i<r) 
         {
            sravn++;
        if(array[i]>array[i+1]) 
                i++;
         }
         else 
            if(i!=r) 
               break;

         sravn++;
         if(temp<=array[i]) 
          break;

         array[j]=array[i]; 
         prisv++;
     }
     array[j] = temp;         prisv++;

      jj++;
    }
 } 


int main()
{int *mas;
int j, l, r,n,i;
 system("cls");
 wcout.imbue(locale("rus_rus.866"));
wcout<<L"Введите кол-во элементов в массиве: ";
cin>>n;
mas= new int [n];
wcout<<L"\n\nИсходный массив:\n";
for ( j = 0; j < n; j ++ ) 
{mas[j]=rand()%100;
cout<<mas[j]<<" ";}
getchar();
wcout<<L"\n\nСортировка по возрастанию"<<endl;
cout<<endl;
HeapSort(mas,n);

wcout<<endl<<L"\nОтсортированный массив: "<<endl;
for(i=0;i<n;i++)
cout<<mas[i]<<" ";
getchar();
wcout<<L"\nСортировка по убыванию"<<endl;
HeapSort1(mas,n);
wcout<<endl<<L"\nОтсортированный массив: "<<endl;
for(i=0;i<n;i++)
cout<<mas[i]<<" ";
getchar();
return 0;
}

Это сообщение отредактировал(а) Jolia - 19.5.2008, 18:31

dizzy1984

Дата 20.5.2008, 08:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 675
Регистрация: 15.2.2007

Репутация: 10
Всего: 25

Я бы помог с комментариями, но найдя вот эту статью http://ru.wikipedia.org/wiki/Пирамидальная_сортировка я думаю, объясню только хуже. Если будут вопросы, задавай.

Jolia

Дата 20.5.2008, 20:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 59
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

статью прочитала, теоретически вроде понятно, но относительно кода вообще туго, не разберу что где и как происходит. Если не сложно все-таки помоги пожалуйста комментариями=)

dizzy1984

Дата 21.5.2008, 10:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 675
Регистрация: 15.2.2007

Репутация: 10
Всего: 25

Только для тебя, Jolia!
Разберу пример для сортировки по возрастанию. Пример беру из википедии.
Рассказываю как понял.
Сортировка строится с использованием бинарного дерева с наложенными на него ограничениями (нет листов с глубиной отличной от максимально возможной более чем на 1 и значение в любой вершине больше или равно значений потомков этой вершины - это для возрастающей сортировки - для убывающей наоборот - значение в любой вершине меньше или равно значений потомков этой вершины). Почему у дерева именно такие особенности - это тема для отдельного разговора (я ничего тут не скажу) поэтому примем это как данность. Так вот странное дерево, СД далее , строящееся в соответствии с входным ветором имеет такую особенность (уже после его полного построения), что в его корне находится самый большой(сортируем по возрастанию) или маленький(сортируем по убыванию) элемент масива. А это уже кое-что. Читай дальше.
Для хранения СД используют обычный массив. Если вершина имеет индекс i, то ее потомки имеют индексы 2i и 2i + 1. Так можно построить СД - помещаем 1-й элемент в корень, 2-ой и 3-й будут его детьми, дети 2-го - 4-й и 5-й и т.д
Процесс сортировки проходит в 2 этапа на первом этапе мы строим СД (в википедии вместо "странное дерево" используют "пирамида", но смысл остается тем же).
Вот код которые его строит

Код


// строим пирамиду
for(i = size / 2 - 1; i >= 0; i-- )
{
    downHeap( a, i, size - 1 );
}

Это подготовительный этап. Используется функция downHeap. Что она делает? Она протаскивает данную ей вершину пока та не перестанет быть причиной неудовлетворения условия "значение в любой вершине больше или равно значений потомков этой вершины". Для построения нормального СД достаточно протащить все вершины, имеющие потомков, т.к вершины без потомков неудовлетворять такому условию не могут в принципе.

Код


template<class T>
void downHeap( T a[], int k, int n )
{
//  процедура просеивания следующего элемента
//  До процедуры: a[k+1]...a[n]  - пирамида
//  После:  a[k]...a[n]  - пирамида
   T new_elem = a[ k ];
// пока у a[k] есть дети
   while( k <= n / 2 )
   {
      int child = 2 * k;
  //  выбираем большего сына
      if( child < n && a[ child ] < a[ child + 1 ] )
         child++;
      if( new_elem >= a[ child ] )
         break;
   // иначе переносим сына наверх
      a[ k ] = a[ child ];
      k = child;
   }
   a[ k ] = new_elem;
}

Ну не знаю как тут прокомментировать кроме уже имеющегося. Повторю!
T new_elem = a[ k ]; // Записываем протаскиваемый элемет, он пригодится позднее
while( k <= n / 2 ) // пока у a[k] есть дети. Т.к для i первый ребенок это 2i, то i>n/2 заведомо бездетен. Он ребенок а дети нас не интересуют.

Код


     int child = 2 * k;
  //  выбираем большего сына
      if( child < n && a[ child ] < a[ child + 1 ] )
         child++;
      if( new_elem >= a[ child ] )
         break;
   // иначе переносим сына наверх
      a[ k ] = a[ child ];
      k = child;

Далее мы определяемся с самым большим ребенком и меняем его с протаскиваемым элементом. Если все в поряде и условие "значение в любой вершине меньше или равно значений потомков этой вершины" выполняется то менять не нужно. Таким образом мы протащили его в следующий узел. Далее процедура повторяется для следующего узла вплоть до бездетных т.к, иначе мы могли бы испортить СД, расположенное ниже текущего.
a[ k ] = new_elem; // Ставим корректное значение протаскиваемого элемента.
На втором этапе мы можем использовать СД для получения последовательности элементов. Это просто - мы берем элемент в корне и ставим его на последнее место - там он и должен стоять при сортировке по возрастанию, после чего нас начинает интересовать только остальные элементы. Элемент незаслуженно стоявший на последнем месте ставится на первое и т.к дерево при этом перестает быть СД, происходит его протаскивание результат которого - новый максимальные элемент нового СД. Процедура повторяется.
Массив отсортирован.

Код


// теперь a[0]...a[size-1] пирамида
   for(i = size - 1; i > 0; i-- )
   {
   // меняем первый с последним
      T temp = a[ i ];
      a[ i ] = a[ 0 ];
      a[ 0 ] = temp;
   // восстанавливаем пирамидальность a[0]...a[i-1]
      downHeap( a, 0, i - 1 );
   }

Вот код который использет эту сортировку

Код


int a [] = {11,27,21,54,75,76,37,28,89,10};
heapSort(a, 10);

И теперь визуализация - если не рисовать граф, то можно показать процесс появления самых больших элементов, набивающихся в конец массива. Т.е сделать вывод массива после строк

Код


      T temp = a[ i ];
      a[ i ] = a[ 0 ];
      a[ 0 ] = temp;

Справишся?

Это сообщение отредактировал(а) dizzy1984 - 21.5.2008, 10:13

Jolia

Дата 22.5.2008, 19:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 59
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

ооо вот это обьяснение) спасибо большооое) слушай, а как переделать код чтоб сортировка выполнялась по убыванию? я попробовала знаки поменять - и нифига не сортирует

dizzy1984

Дата 23.5.2008, 07:34 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 675
Регистрация: 15.2.2007

Репутация: 10
Всего: 25

А я говорил smile

Код


while( k <= n / 2 )
   {
      int child = 2 * k;
  //  выбираем большего сына
      if( child < n && a[ child ] > a[ child + 1 ] )
         child++;
      if( new_elem <= a[ child ] )
         break;

Jolia

Дата 25.5.2008, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 59
Регистрация: 12.3.2007

Репутация: нет
Всего: нет

Спасибо4ки большушее)))

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »