Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 4,291: / Line 4,291: @@
 =={{header|Pascal}}==
+{{works with|FPC}}
 An example, which works on arrays with arbitrary bounds :-)
-<syntaxhighlight lang="pascal">program HeapSortDemo;
+<syntaxhighlight lang="pascal">
+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 heapify(var a: TIntArray);
+procedure HeapSort(var a: array of Integer);
+  procedure SiftDown(Root, Last: Integer);
   var
-    start, count: integer;
+    Child, Tmp: Integer;
   begin
+    while Root * 2 + 1 <= Last do begin
-    count := length(a);
-    start := low(a) + count div 2 - 1;
+      Child := Root * 2 + 1;
+      if (Child + 1 <= Last) and (a[Child] < a[Child + 1]) then
-    while start >= low(a) do
-    begin
+        Inc(Child);
+      if a[Root] < a[Child] then begin
-      siftdown(a, start, high(a));
-      dec(start);
+        Tmp := a[Root];
+        a[Root] := a[Child];
+        a[Child] := Tmp;
+        Root := Child;
+      end else exit;
     end;
   end;
+var
+  I, Tmp: Integer;
-procedure heapSort(var a: TIntArray);
+begin
-  var
+  for I := Length(a) div 2 downto 0 do
-    ende, swap: integer;
+    SiftDown(I, High(a));
-  begin
+  for I := High(a) downto 1 do begin
-    heapify(a);
-    ende := high(a);
+    Tmp := a[0];
-    while ende > low(a) do
+    a[0] := a[I];
-    begin
+    a[I] := Tmp;
-      swap := a[low(a)];
+    SiftDown(0, I - 1);
-      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 := low(data) to high(data) do
+    Write(A[I], ', ');
+  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
-    write(data[i]:4);
+  HeapSort(a2);
+  PrintArray('a2', a2);
-  end;
+end.
-  writeln;
-end.</syntaxhighlight>
+</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]
-13   0   1   0  14  13  10   1  10   9   2
-The data after sorting:
-0   1   1   2   9  10  10  12  13  13  14
 </pre>