Реализации алгоритмов/Сортировка/Пирамидальная: различия между версиями
Содержимое удалено Содержимое добавлено
→C++ (другой вариант): Нормальное оформление кода |
Нормальное форматирование кода на Паскале; языки следуют в алфавитном порядке |
||
Строка 1:
{{wikipedia|Пирамидальная сортировка}}
==
<source lang="c">
#include <stdio.h>
Строка 59:
</source>
==
===Вариант № 1===
<source lang="cpp">
#include <iterator>
Строка 114 ⟶ 115 :
</source>
===Вариант № 2===
<source lang="cpp">
#include <iostream>
Строка 180 ⟶ 181 :
==[[w:C Sharp|C#]]==
===Вариант № 1===
<source lang="csharp">
static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)
Строка 254 ⟶ 256 :
</source>
===Вариант № 2===
<source lang="csharp">
public class Heap<T>
Строка 328 ⟶ 330 :
heap.HeapSort();
}
</source>
Здесь T - любой тип, на множестве элементов которого можно ввести [[w:Частично упорядоченное множество|отношение частичного порядка]].
==[[w:Java|Java]]==
<source lang="java">
/**
Строка 671 ⟶ 442 :
}
</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>
| |||