Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями

Нормальное форматирование кода на Паскале; языки следуют в алфавитном порядке
(→‎C++ (другой вариант): Нормальное оформление кода)
(Нормальное форматирование кода на Паскале; языки следуют в алфавитном порядке)
{{wikipedia|Пирамидальная сортировка}}
 
== [[w:Си (язык программирования)|C]] ==
<source lang="c">
#include <stdio.h>
</source>
 
== [[w:C++|C++]] ==
===Вариант № 1===
<source lang="cpp">
#include <iterator>
</source>
 
===Вариант № 2===
== C++ (другой вариант) ==
<source lang="cpp">
#include <iostream>
 
==[[w:C Sharp|C#]]==
===Вариант № 1===
<source lang="csharp">
static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)
</source>
 
===Вариант № 2===
== C# (другой вариант) ==
<source lang="csharp">
public class Heap<T>
heap.HeapSort();
}
 
</source>
Здесь T - любой тип, на множестве элементов которого можно ввести [[w:Частично упорядоченное множество|отношение частичного порядка]].
 
== [[w:Pascal|Pascal]] ==
 
==[[w:Java|Java]]==
Вместо '''«SomeType»''' следует подставить любой из арифметических типов (например [[integer]]).
 
<source lang="pascal">
procedure Sort(var Arr: array of SomeType; Count: Integer);
 
procedure DownHeap(index, Count: integer; Current: SomeType);
//Функция пробегает по пирамиде восстанавливая ее
//Также используется для изначального создания пирамиды
//Использование: Передать номер следующего элемента в index
//Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
var
Child: Integer;
begin
while index < Count div 2 do begin
Child := (index+1)*2-1;
if (Child < Count-1) and (Arr[Child] < Arr[Child+1]) then
Child:=Child+1;
if Current >= Arr[Child] then
break;
Arr[index] := Arr[Child];
index := Child;
end;
Arr[index] := Current;
end;
 
//Основная функция
var
i: integer;
Current: SomeType;
begin
//Собираем пирамиду
for i := (Count div 2)-1 downto 0 do
DownHeap(i, Count, Arr[i]);
//Пирамида собрана. Теперь сортируем
for i := Count-1 downto 0 do begin
Current := Arr[i]; //перемещаем верхушку в начало отсортированного списка
Arr[i] := Arr[0];
DownHeap(0, i, Current); //находим нужное место в пирамиде для нового элемента
end;
end;
</source>
здесь нет ввывода и ввода массива лиибо рандома , либо пользователем
 
== Pascal (другой вариант) ==
Примечание:
myarray = array[1..Size] of integer;
N — количество элементов массива
 
<source lang="pascal">
procedure HeapSort(var m: myarray; N: integer);
var
i: integer;
 
procedure Swap(var a,b:integer);
var
tmp: integer;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
 
procedure Sort(Ns: integer);
var
i, tmp, pos, mid: integer;
begin
mid := Ns div 2;
for i := mid downto 1 do
begin
pos := i;
while pos<=mid do
begin
tmp := pos*2;
if tmp<Ns then
begin
if m[tmp+1]<m[tmp] then
tmp := tmp+1;
if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := tmp;
end
else
pos := Ns;
end
else
if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := Ns;
end
else
pos := Ns;
end;
end;
end;
begin
for i:=N downto 2 do
begin
Sort(i);
Swap(m[1], m[i]);
end;
end;
</source>
 
== Pascal (третий вариант) ==
<source lang="pascal">
//процедура для перессылки записей
procedure swap(var x,y:integer);
var temp:integer;
begin
temp:=x;
x:=y;
y:=temp;
end;
 
//процедура приведения массива к пирамидальному виду (to pyramide)
procedure toPyr(var data:TArray; n:integer); //n - размерность массива
var i:integer;
begin
for i:=n div 2 downto 1 do begin
if 2*i<=n then if data[i]<data[2*i] then swap(data[i],data[2*i]);
if 2*i+1<=n then if data[i]<data[2*i+1] then swap(data[i],data[2*i+1]);
end;
end;
 
//процедура для сдвига массива влево
procedure left(var data:TArray; n:integer);
var i:integer;
temp:integer;
begin
temp:=data[1];
for i:=1 to n-1 do
data[i]:=data[i+1];
data[n]:=temp;
end;
 
//основная программа
begin
for i:=n downto 1 do begin
topyr(a,i);
left(a,n);
end;
</source>
 
== [[w:Python|Python]] ==
<source lang="python">
def heapSort(li):
"""Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
 
def downHeap(li, k, n):
new_elem = li[k]
while 2*k+1 < n:
child = 2*k+1
if child+1 < n and li[child] < li[child+1]:
child += 1
if new_elem >= li[child]:
break
li[k] = li[child]
k = child
li[k] = new_elem
 
size = len(li)
for i in range(size//2-1,-1,-1):
downHeap(li, i, size)
for i in range(size-1,0,-1):
temp = li[i]
li[i] = li[0]
li[0] = temp
downHeap(li, 0, i)
</source>
 
== [[w:Python|Python]] (другой вариант) ==
 
<source lang="python">
def heapsort(s):
sl = len(s)
 
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
 
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+2 < unsorted:
gtci = i_gt(pi*2+1, pi*2+2)
swap(pi, gtci)
pi = gtci
# heapify
for i in range((sl/2)-1, -1, -1):
sift(i, sl)
# sort
for i in range(sl-1, 0, -1):
swap(i, 0)
sift(0, i)
</source>
 
== [[w:Perl|Perl]] ==
<source lang="perl">
@out=(6,4,2,8,5,3,1,6,8,4,3,2,7,9,1)
$N=@out+0;
if($N>1){
while($sh+2!=$N){
$b=undef;
for my$i(0..$N-1){
if($i*2+2+$sh<$N){
if($out[$i+$sh]gt$out[$i*2+1+$sh] || $out[$i+$sh]gt$out[$i*2+2+$sh]){
if($out[$i*2+1+$sh]lt$out[$i*2+2+$sh]){
($out[$i*2+1+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+1+$sh]);
$b=1;
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+2+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+2+$sh]);
$b=1;
}
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+1+$sh],$out[$i*2+2+$sh])=($out[$i*2+2+$sh],$out[$i*2+1+$sh]);
$b=1;
}
}elsif($i*2+1+$sh<$N && $out[$i+$sh]gt$out[$i*2+1+$sh]){
($out[$i+$sh],$out[$i*2+1+$sh])=($out[$i*2+1+$sh],$out[$i+$sh]);
$b=1;
}
}
++$sh if!$b;
last if$sh+2==$N;
}
}
</source>
 
== [[w:Java|Java]] ==
<source lang="java">
/**
}
</source>
 
==[[w:Pascal|Pascal]]==
===Вариант № 1===
Вместо '''«SomeType»''' следует подставить любой из арифметических типов (например [[integer]]).
 
<source lang="pascal">
procedure Sort(var Arr: array of SomeType; Count: Integer);
 
procedure DownHeap(index, Count: integer; Current: SomeType);
{
Функция пробегает по пирамиде восстанавливая ее
Также используется для изначального создания пирамиды
Использование: Передать номер следующего элемента в index
Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
}
var Child: Integer;
begin
while index < Count div 2 do begin
Child := (index+1)*2-1;
if (Child < Count-1) and (Arr[Child] < Arr[Child+1]) then
Child:=Child+1;
if Current >= Arr[Child] then
break;
Arr[index] := Arr[Child];
index := Child
end;
Arr[index] := Current
end;
 
{ Основная функция }
var i: integer;
Current: SomeType;
begin
{ Собираем пирамиду }
for i := (Count div 2)-1 downto 0 do
DownHeap(i, Count, Arr[i]);
{ Пирамида собрана. Теперь сортируем }
for i := Count-1 downto 0 do
begin
Current := Arr[i]; { перемещаем верхушку в начало отсортированного списка }
Arr[i] := Arr[0];
DownHeap(0, i, Current) { находим нужное место в пирамиде для нового элемента }
end
end;
</source>
Здесь нет вывода и ввода массива. Либо случайный, либо пользователем.
 
===Вариант № 2===
Примечание:
myarray = array[1..Size] of integer;
N — количество элементов массива
 
<source lang="pascal">
procedure HeapSort(var m: myarray; N: integer);
var i: integer;
procedure Swap(var a,b:integer);
var tmp: integer;
begin
tmp := a;
a := b;
b := tmp
end;
 
procedure Sort(Ns: integer);
var i, tmp, pos, mid: integer;
begin
mid := Ns div 2;
for i := mid downto 1 do
begin
pos := i;
while pos<=mid do
begin
tmp := pos*2;
if tmp<Ns then
begin
if m[tmp+1]<m[tmp] then
tmp := tmp+1;
if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := tmp
end
else
pos := Ns
end
else if m[pos]>m[tmp] then
begin
Swap(m[pos], m[tmp]);
pos := Ns
end
else
pos := Ns
end
end
end;
begin
for i := N downTo 2 do
begin
Sort(i);
Swap(m[1], m[i])
end
end;
</source>
 
===Вариант № 3===
<source lang="pascal">
{ Процедура для обмена значений переменных }
procedure swap (var x, y: integer);
var temp: integer;
begin
temp := x;
x := y;
y := temp
end;
 
{ Процедура приведения массива к пирамидальному виду (to heap) }
procedure toHeap (var data: TArray; n: integer); { n - размер массива }
var i: integer;
begin
for i := n div 2 downTo 1 do
begin
if 2 * i <= n then
if data[i] < data[2 * i] then
swap(data[i], data[2 * i]);
if 2 * i + 1 <= n then
if data[i] < data[2 * i + 1] then
swap(data[i], data[2 * i + 1])
end
end;
 
{ Процедура для сдвига массива влево }
procedure left (var data: TArray; n: integer);
var i: integer;
temp: integer;
begin
temp := data[1];
for i := 1 to n - 1 do
data[i] := data[i + 1];
data[n] := temp
end;
 
{ Основная программа }
BEGIN
for i := n downTo 1 do
begin
toHeap(a, i);
left(a, n);
end
END.
</source>
 
==[[w:Perl|Perl]]==
<source lang="perl">
@out=(6,4,2,8,5,3,1,6,8,4,3,2,7,9,1)
$N=@out+0;
if($N>1){
while($sh+2!=$N){
$b=undef;
for my$i(0..$N-1){
if($i*2+2+$sh<$N){
if($out[$i+$sh]gt$out[$i*2+1+$sh] || $out[$i+$sh]gt$out[$i*2+2+$sh]){
if($out[$i*2+1+$sh]lt$out[$i*2+2+$sh]){
($out[$i*2+1+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+1+$sh]);
$b=1;
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+2+$sh],$out[$i+$sh])=($out[$i+$sh],$out[$i*2+2+$sh]);
$b=1;
}
}elsif($out[$i*2+2+$sh]lt$out[$i*2+1+$sh]){
($out[$i*2+1+$sh],$out[$i*2+2+$sh])=($out[$i*2+2+$sh],$out[$i*2+1+$sh]);
$b=1;
}
}elsif($i*2+1+$sh<$N && $out[$i+$sh]gt$out[$i*2+1+$sh]){
($out[$i+$sh],$out[$i*2+1+$sh])=($out[$i*2+1+$sh],$out[$i+$sh]);
$b=1;
}
}
++$sh if!$b;
last if$sh+2==$N;
}
}
</source>
 
==[[w:Python|Python]]==
===Вариант № 1===
<source lang="python">
def heapSort(li):
"""Сортирует список в возрастающем порядке с помощью алгоритма пирамидальной сортировки"""
 
def downHeap(li, k, n):
new_elem = li[k]
while 2*k+1 < n:
child = 2*k+1
if child+1 < n and li[child] < li[child+1]:
child += 1
if new_elem >= li[child]:
break
li[k] = li[child]
k = child
li[k] = new_elem
 
size = len(li)
for i in range(size//2-1,-1,-1):
downHeap(li, i, size)
for i in range(size-1,0,-1):
temp = li[i]
li[i] = li[0]
li[0] = temp
downHeap(li, 0, i)
</source>
 
===Вариант № 2===
<source lang="python">
def heapsort(s):
sl = len(s)
 
def swap(pi, ci):
if s[pi] < s[ci]:
s[pi], s[ci] = s[ci], s[pi]
 
def sift(pi, unsorted):
i_gt = lambda a, b: a if s[a] > s[b] else b
while pi*2+2 < unsorted:
gtci = i_gt(pi*2+1, pi*2+2)
swap(pi, gtci)
pi = gtci
# heapify
for i in range((sl/2)-1, -1, -1):
sift(i, sl)
# sort
for i in range(sl-1, 0, -1):
swap(i, 0)
sift(0, i)
</source>
 
Анонимный участник