1------------------------------------------------------------------------------ 2-- -- 3-- GNAT RUN-TIME COMPONENTS -- 4-- -- 5-- G N A T . H E A P _ S O R T _ G -- 6-- -- 7-- B o d y -- 8-- -- 9-- Copyright (C) 1995-2010, AdaCore -- 10-- -- 11-- GNAT is free software; you can redistribute it and/or modify it under -- 12-- terms of the GNU General Public License as published by the Free Soft- -- 13-- ware Foundation; either version 3, or (at your option) any later ver- -- 14-- sion. GNAT is distributed in the hope that it will be useful, but WITH- -- 15-- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -- 16-- or FITNESS FOR A PARTICULAR PURPOSE. -- 17-- -- 18-- As a special exception under Section 7 of GPL version 3, you are granted -- 19-- additional permissions described in the GCC Runtime Library Exception, -- 20-- version 3.1, as published by the Free Software Foundation. -- 21-- -- 22-- You should have received a copy of the GNU General Public License and -- 23-- a copy of the GCC Runtime Library Exception along with this program; -- 24-- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -- 25-- <http://www.gnu.org/licenses/>. -- 26-- -- 27-- GNAT was originally developed by the GNAT team at New York University. -- 28-- Extensive contributions were provided by Ada Core Technologies Inc. -- 29-- -- 30------------------------------------------------------------------------------ 31 32package body GNAT.Heap_Sort_G is 33 34 ---------- 35 -- Sort -- 36 ---------- 37 38 -- We are using the classical heapsort algorithm (i.e. Floyd's Treesort3) 39 -- as described by Knuth ("The Art of Programming", Volume III, first 40 -- edition, section 5.2.3, p. 145-147) with the modification that is 41 -- mentioned in exercise 18. For more details on this algorithm, see 42 -- Robert B. K. Dewar PhD thesis "The use of Computers in the X-ray 43 -- Phase Problem". University of Chicago, 1968, which was the first 44 -- publication of the modification, which reduces the number of compares 45 -- from 2NlogN to NlogN. 46 47 procedure Sort (N : Natural) is 48 49 Max : Natural := N; 50 -- Current Max index in tree being sifted 51 52 procedure Sift (S : Positive); 53 -- This procedure sifts up node S, i.e. converts the subtree rooted 54 -- at node S into a heap, given the precondition that any sons of 55 -- S are already heaps. On entry, the contents of node S is found 56 -- in the temporary (index 0), the actual contents of node S on 57 -- entry are irrelevant. This is just a minor optimization to avoid 58 -- what would otherwise be two junk moves in phase two of the sort. 59 60 ---------- 61 -- Sift -- 62 ---------- 63 64 procedure Sift (S : Positive) is 65 C : Positive := S; 66 Son : Positive; 67 Father : Positive; 68 -- Note: by making the above all Positive, we ensure that a test 69 -- against zero for the temporary location can be resolved on the 70 -- basis of types when the routines are inlined. 71 72 begin 73 -- This is where the optimization is done, normally we would do a 74 -- comparison at each stage between the current node and the larger 75 -- of the two sons, and continue the sift only if the current node 76 -- was less than this maximum. In this modified optimized version, 77 -- we assume that the current node will be less than the larger 78 -- son, and unconditionally sift up. Then when we get to the bottom 79 -- of the tree, we check parents to make sure that we did not make 80 -- a mistake. This roughly cuts the number of comparisons in half, 81 -- since it is almost always the case that our assumption is correct. 82 83 -- Loop to pull up larger sons 84 85 loop 86 Son := 2 * C; 87 88 if Son < Max then 89 if Lt (Son, Son + 1) then 90 Son := Son + 1; 91 end if; 92 elsif Son > Max then 93 exit; 94 end if; 95 96 Move (Son, C); 97 C := Son; 98 end loop; 99 100 -- Loop to check fathers 101 102 while C /= S loop 103 Father := C / 2; 104 105 if Lt (Father, 0) then 106 Move (Father, C); 107 C := Father; 108 else 109 exit; 110 end if; 111 end loop; 112 113 -- Last step is to pop the sifted node into place 114 115 Move (0, C); 116 end Sift; 117 118 -- Start of processing for Sort 119 120 begin 121 -- Phase one of heapsort is to build the heap. This is done by 122 -- sifting nodes N/2 .. 1 in sequence. 123 124 for J in reverse 1 .. N / 2 loop 125 Move (J, 0); 126 Sift (J); 127 end loop; 128 129 -- In phase 2, the largest node is moved to end, reducing the size 130 -- of the tree by one, and the displaced node is sifted down from 131 -- the top, so that the largest node is again at the top. 132 133 while Max > 1 loop 134 Move (Max, 0); 135 Move (1, Max); 136 Max := Max - 1; 137 Sift (1); 138 end loop; 139 140 end Sort; 141 142end GNAT.Heap_Sort_G; 143