Rosetta Code

Sorting algorithms/Heapsort: Difference between revisions

Page Discussion

Sorting algorithms/Heapsort (view source)

Revision as of 08:34, 1 November 2022

299 bytes removed ,  1 year ago
→‎{{header|Pascal}}: replaced incorrect previous version
(→‎{{header|Pascal}}: replaced incorrect previous version)
Line 4,291:
 
=={{header|Pascal}}==
{{works with|FPC}}
An example, which works on arrays with arbitrary bounds :-)
<syntaxhighlight lang="pascal">program HeapSortDemo;
program HeapSortDemo;
 
{$mode objfpc}{$h+}{$b-}
type
TIntArray = array[4..15] of integer;
var▼
data: TIntArray;
i: integer;
procedure siftDown(var a: TIntArray; start, ende: integer);
var▼
root, child, swap: integer;
begin▼
root := start;▼
while root * 2 - start + 1 <= ende do▼
begin▼
child := root * 2 - start + 1;
if (child + 1 <= ende) and (a[child] < a[child + 1]) then▼
inc(child);
if a[root] < a[child] then▼
begin
swap := a[root];
a[root] := a[child];▼
a[child] := swap;▼
root := child;
end▼
else
exit;
end;▼
end;▼
 
procedure heapifyHeapSort(var a: TIntArrayarray of Integer);
procedure SiftDown(Root, Last: Integer);
var
startChild, countTmp: integerInteger;
begin
▲ while rootRoot * 2 - start + 1 <= endeLast do begin
count := length(a);
start Child := low(a)Root + count div* 2 -+ 1;
▲ if (childChild + 1 <= endeLast) and (a[childChild] < a[childChild + 1]) then
while start >= low(a) do
begin Inc(Child);
▲ if a[rootRoot] < a[childChild] then begin
siftdown(a, start, high(a));
dec(start) Tmp := a[Root];
▲ a[rootRoot] := a[childChild];
▲ a[childChild] := swapTmp;
▲ root Root := startChild;
▲ end else exit;
end;
end;
▲var
 
I, Tmp: Integer;
procedure heapSort(var a: TIntArray);
▲ begin
var▼
for iI := lowLength(dataa) todiv high(data)2 downto 0 do▼
ende, swap: integer;
SiftDown(I, High(a));
begin
for I := High(a) downto 1 do begin
heapify(a);
endeTmp := high(a)[0];
whilea[0] ende:= > low(a) do[I];
begina[I] := Tmp;
SiftDown(0, I swap- := a[low(a1)];
a[low(a)] := a[ende];
a[ende] := swap;
dec(ende);
siftdown(a, low(a), ende);
end;
end;
▲ end;
 
procedure PrintArray(const Name: string; const A: array of Integer);
▲ var
I: Integer;
begin
Write(Name, ': [');
Randomize;
for I := 0 to High(A) - 1 do
writeln('The data before sorting:');
for i := lowWrite(data)A[I], to', high(data') do;
WriteLn(A[High(A)], ']');
begin
▲ end;
data[i] := Random(high(data));
 
write(data[i]:4);
▲ var
end;▼
a1: array[-7..5] of Integer = (-34, -20, 30, 13, 36, -10, 5, -25, 9, 19, 35, -50, 29);
writeln;
a2: array of Integer = (-9, 42, -38, -5, -38, 0, 0, -15, 37, 7, -7, 40);
heapSort(data);
▲ begin
writeln('The data after sorting:');
HeapSort(a1);
▲ for i := low(data) to high(data) do
PrintArray('a1', a1);
begin
writeHeapSort(data[i]:4a2);
PrintArray('a2', a2);
end;
▲ end;.
writeln;
end.</syntaxhighlight>
{{out}}
<pre>
a1: [-50, -34, -25, -20, -10, 5, 9, 13, 19, 29, 30, 35, 36]
The data before sorting:
a2: [-38, -38, -15, -9, -7, -5, 0, 0, 7, 37, 40, 42]
12 13 0 1 0 14 13 10 1 10 9 2
The data after sorting:
0 0 1 1 2 9 10 10 12 13 13 14
</pre>
 
Avk
73

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333021"