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


Добавил:DMT
Дата создания:23 апреля 2008, 22:16
Дата обновления:25 апреля 2008, 12:47
Просмотров:8190 последний сегодня, 6:09
Комментариев: 0

Элементы произвольного массива можно рассматривать как узлы дерева, для которых индексы массива имеют назначения, аналогичные тем, которые они имели в турнике с выбыванием:

i =1 – корень дерева,

2 i – левый сын i - го элемента,

2 i +1 – правый сын i -го элемента,

i /2 – отец i -го элемента.

Информационная часть i -го элемента будет равна x [ i ] . Здесь i /2 – целая часть дроби . Если для всех i , таких, что и , имеют место неравенства , то массив называется пирамидой . На рис изображена пирамида, состоящая из 10 элементов.

Она соотвествует массиву

x 1 =10, x 2 =20, x 3 =15, x 4 =23, x 5 =28, x 6 =30, x 7 =16, x 8 =24, x 9 =40, x 10 =29.

Обобщим понятие пирамидальности на части массива. Массив x называется пирамидальным в части l : u , где 1 ? l ? u ? n , если неравенство x[i/2] ? x[i] имеет место для каждого i , удовлетворяющего соотношениям l ? i/2 и i ? u .

Если к пирамиде добавить элемент x n +1 , то свойство пирамидальности в части 1: n за шагов можно расширить до свойства пирамидальности в части 1: n +1 , меняя в цикле местами с отцом элемент, в котором нарушается свойство пирамидальности. Например , если к пирамиде на рис добавить x 11 =18 , то надо переставить местами элементы 18 и 28, а потом – 18 и 20. Получим пирамиду, приведенную на рис.

Пусть SiftUp ( int i ) – подпрограмма, расширяющая свойство пирамидальности в части 1: i -1 до свойства пирамидальности в части 1: i . Тогда легко построить пирамиду, состоящую из элементов массива x [1],..., x [ n ]. Это делается с помощью цикла

for ( i =2; i <= n ; i ++)

SiftUp ( i );

после которого 1271 наименьший элемент массива будет находиться в корне и будет равен x [1].

Если теперь выбрать этот наименьший элемент и на его место поставить последний элемент, то для нахождения наименьшего среди оставшихся достаточно расширить свойство пирамидальности в части 2: n -1 до пирамидальности массива x в части 1: n -1 . Повторение этого процесса приводит к одному из видов сортировки выбором – к пирамидальной сортировке .

Пусть SiftDown ( int i ) – подпрограмма, расширяющая свойство пирамидальности массива x в части 2: i до свойства пирамидальности в части 1: i . Тогда для реализации пирамидальной сортировки достаточно следующих операторов:

for(i=2; i<=n; i++)

SiftUp(i);

for(i=n; i>=2; i--)

{

swap(&x[1], &x[i]; SiftDown(i-1));

}

В первом цикле будет построена пирамида с наименьшим элементом x [1] . Во втором цикле элемент x [1] переставляется с последним, в результате чего наименьший элемент оказывается в конце массива. Затем пирамидальность части 2: n -1 распространяется на часть 1: n -1 . Затем вновь x [1] переставляется с x [ n -1] и пирамидальность части 2: n -2 распространяется на часть 1: n -2 , и т.д. В результате элементы массива x будут расположены в порядке невозрастания x [1] ? x [2] ? ... ? x [ n ].

Разработаем подпрограммы SiftUp () и SiftDown (). Расширение пирамидальности в части 1: n -1 до пирамидальности в части 1: n осуществляется сравнением x [ n ] с предками узла n .

void SiftUp(int n)

// Heap(1,n-1) ? Heap(1,n)

{

int i = n , p ;

while ( i >1) // пока не достигли корня

{

p=i/2; // индекс отца

if(x[p]<=x[i]) break; // выход из цикла

swap(&x[p],&x[i]); // если x[p]>x[i]

i = p ; // движемся наверх

}

}

Расширение пирамидальности в части 2:n до пирамидальности в части 1:n осуществляется с помощью сравнения x[1] с потомками, и перестановками с меньшими из них.

void SiftDown(int n)

// Heap(2,n) ? Heap(1,n)

{

int i=1,c;

while((c=2*i)<=n)

{

// c – левый сын узла i

if (( c +1)<= n ) // c +1 – правый сын

if ( x [ c +1]< x [ c ])

c = c +1; // наименьший сын

if(x[i]<=x[c]) break; // выход из цикла

swap (& x [ c ],& x [ i ]); // движение вниз

i = c ;

}

}

Приведем окончательный текст программы для сортировки массива по убыванию.

#include<conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

int x[11];

void swap(int *a, int *b)

{

int temp=*a;

*a=*b;

*b=temp;

}

 

void SiftUp(int n)

{

int i = n , p ;

while ( i >1) //пока не достигнут корень

{

p = i /2; //индекс сдвига

if ( x [ p ]<= x [ i ]) break ; //выход из цикла

swap(&x[p],&x[i]); // если x[p] > x[i]

i = p ; //то движение наверх

}

}

void SiftDown(int n)

{

int i=1,c;

while (( c =2* i )<= n ) //с – левый сын узла

{

if (( c +1)<= n ) //с+1 – пра 49f вый сын узла

if ( x [ c +1]< x [ c ])

c = c +1; //наименьший сын

if(x[i]<=x[c]) break; // выход из цикла

swap (& x [ c ],& x [ i ]); //движение вниз

i=c;

}

}

 

main()

{

int i;

randomize();

for(i=1; i<=10; i++)

x[i]=rand();

clrscr();

printf(" До сортировки :\n");

for(i=1; i<=10; i++)

printf("%d ",x[i]);

for(i=2; i<=10; i++)

SiftUp(i);

for(i=10; i>=2; i--)

{

swap(&x[1], &x[i]);

SiftDown(i-1);

}

printf("\n После сортировки :\n");

for(i=1; i<=10; i++)

printf("%d ",x[i]);

}

Результаты работы программы

До сортировки:

30316 7564 18987 7484 5556 25673 1984 21007 18977 18770

После сортировки:

30316 25673 21007 18987 18977 18770 7564 7484 5556 1984

Новый исходник: 
Код на C++
  1. #include<conio.h>
  2. #include <iostream.h>
  3. #include <stdlib.h>
  4.  
  5. class Racio
  6. {
  7. public:
  8.  float chisl;//числитель
  9.  float znamen;//знаменатель
  10.  
  11.  
  12.  Racio() {};//конструктор по умолчанию
  13.  Racio(float c, float z)
  14. 	{
  15. 	chisl=c;
  16. 	znamen=z; socr();
  17. 	}//конструктор
  18. ~Racio() {}//деструктор
  19.  
  20. void socr() //сокращение
  21. {
  22. if(znamen==0) {cout << "Ошибка"; exit(1);}//ноль недопустим
  23. float a=chisl;
  24. float b=znamen;
  25. if(chisl==0) {znamen=1;return;}//ноль недопустим
  26. if(a<0){a=-a;};
  27. if(b<0){b=-b;};
  28. //Сокращение дроби
  29. while (a!=b)
  30. {
  31.  if(a>b) a=a-b;
  32.  if(b>a) b=b-a;
  33. }
  34. chisl=chisl/a;
  35. znamen=znamen/a;
  36. }
  37.  
  38.  int operator==(Racio &obj);//перегрузка оператора =
  39.  void operator=(Racio &obj);//перегрузка оператора ==
  40.  int operator<(Racio &obj);//перегрузка оператора <
  41.  int operator<=(Racio &obj);//перегрузка оператора <=
  42.  int operator>(Racio &obj);//перегрузка оператора >
  43.  int operator>=(Racio &obj);//перегрузка оператора >=
  44.  
  45.  // Перегрузка оператора << для вывода класса Racio
  46.  friend ostream &operator<<(ostream &, Racio &);
  47. };
  48.  
  49. //Перегрузка ==
  50. int Racio::operator==(Racio &obj)
  51. {
  52.  if(chisl==obj.chisl&&znamen==obj.znamen)return 1;
  53.  else
  54.  return 0;
  55. }
  56.  
  57. //Перегрузка =
  58. void Racio::operator=(Racio &obj)
  59. {
  60. chisl=obj.chisl;
  61. znamen=obj.znamen;
  62. }
  63.  
  64. //Перегрузка <
  65. int Racio::operator<(Racio &obj)
  66. {
  67.  float d1=chisl/znamen;
  68.  float d2=obj.chisl/obj.znamen;
  69.  if(d1<d2)return 1;
  70.  return 0;
  71. }
  72.  
  73. //Перегрузка <=
  74. int Racio::operator<=(Racio &obj)
  75. {
  76.  float d1=chisl/znamen;
  77.  float d2=obj.chisl/obj.znamen;
  78.  if(d1<=d2)return 1;
  79.  return 0;
  80. }
  81.  
  82.  
  83.  
  84. //Перегрузка >
  85. int Racio::operator>(Racio &obj)
  86. {
  87.  float d1=chisl/znamen;
  88.  float d2=obj.chisl/obj.znamen;
  89.  if(d1>d2)return 1;
  90.  return 0;
  91. }
  92.  
  93. //Перегрузка >=
  94. int Racio::operator>=(Racio &obj)
  95. {
  96.  float d1=chisl/znamen;
  97.  float d2=obj.chisl/obj.znamen;
  98.  if(d1>=d2)return 1;
  99.  return 0;
  100. }
  101.  
  102.  
  103. //Перегрузка оператора <<
  104. ostream &operator<< (ostream &fo, Racio &fp)
  105. {
  106. fo << fp.chisl << "/" <<fp.znamen<<"  ";
  107. return fo;
  108. }
  109.  
  110.  
  111. template <class Type>
  112. void swap(Type *a, Type *b)
  113. {
  114. 	Type temp=*a;
  115. 	*a=*b;
  116. 	*b=temp;
  117. }
  118. template <class Type>
  119. void SiftUp(Type *x,int n)
  120. {
  121. 	int i=n,p;
  122. 	while(i>1)	//пока не достигнут корень
  123. 	{
  124. 		p=i/2;	//индекс сдвига
  125. 		if(x[p]>=x[i]) break;	//выход из цикла
  126. 		swap(&x[p],&x[i]);	//если x[p] > x[i]
  127. 		i=p;				//то движение наверх
  128. 	}
  129. }
  130. template <class Type>
  131. void SiftDown(Type *x,int n)
  132. {
  133. 	int i=1,c;
  134. 	while((c=2*i)<=n)		//с – левый сын узла
  135. 	{
  136. 		if((c+1)<=n)		//с+1 – правый сын узла
  137. 		  if(x[c+1]>x[c])
  138. 			c=c+1;		//наименьший сын
  139. 		if(x[i]>=x[c]) break;	//выход из цикла
  140. 		swap(&x[c],&x[i]);	//движение вниз
  141. 		i=c;
  142. 	}
  143. }
  144.  
  145. main()
  146. {
  147. clrscr();
  148. gotoxy(25,1);
  149. cout<<"ПИРАМИДАЛЬНАЯ СОРТИРОВКА";
  150.  
  151. int y[11];
  152. 	int i;
  153. 	randomize();
  154. 	for(i=1; i<=10; i++) y[i]=random(10);
  155.  
  156. 	cout<<"\nРяд целых чисел"<<'\n';
  157. 	for(i=1; i<=10; i++) cout<<' '<<y[i];
  158.  
  159. 	for(i=2; i<=10; i++) SiftUp(y,i);
  160. 	for(i=10; i>=2; i--)
  161. 	{
  162. 		swap(&y[1], &y[i]);
  163. 		SiftDown(y,i-1);
  164. 	}
  165.  
  166. 	cout<<"\nОтсортированный ряд"<<'\n';
  167.  
  168. 	for(i=1; i<=10; i++) cout<<' '<<y[i];
  169.  
  170.  
  171. float x[11];
  172. 	for(i=1; i<=10; i++) x[i]=random(10)*0.1;
  173.  
  174. 	cout<<"\n\nРяд чисел c плавующей точкой"<<'\n';
  175. 	for(i=1; i<=10; i++) cout<<' '<<x[i];
  176.  
  177. 	for(i=2; i<=10; i++) SiftUp(x,i);
  178. 	for(i=10; i>=2; i--)
  179. 	{
  180. 		swap(&x[1], &x[i]);
  181. 		SiftDown(x,i-1);
  182. 	}
  183.  
  184. 	cout<<"\nОтсортированный ряд"<<'\n';
  185.  
  186. 	for(i=1; i<=10; i++) cout<<' '<<x[i];
  187.  
  188.  
  189. //Рациональные числа
  190. Racio r[11];
  191. 	float xi;
  192. 	for(i=1; i<=10; i++)
  193. 	{
  194. 	//r[i].chisl=random(8)+1;
  195.  
  196. 	 r[i]=Racio(random(8)-5,random(10)+1);
  197. 	//do{r[i].znamen=random(10)+1;}while(r[i].znamen<=r[i].chisl);
  198. 	//r[i].socr();
  199. 	}
  200. 	cout<<"\n\nРяд рациональных чисел "<<'\n';
  201. 	for(i=1; i<=10; i++) cout<<' '<<r[i];
  202.  
  203. 	for(i=2; i<=10; i++) SiftUp(r,i);
  204. 	for(i=10; i>=2; i--)
  205. 	{
  206. 		swap(&r[1], &r[i]);
  207. 		SiftDown(r,i-1);
  208. 	}
  209.  
  210. 	cout<<"\nОтсортированный ряд"<<'\n';
  211.  
  212. 	for(i=1; i<=10; i++) cout<<' '<<r[i];
  213.  
  214. getch();
  215. return 0;
  216. }
При использовании обязательна ссылка на http://DMTSoft.ru
up