1------------------------------------------------------------------------------ 2-- -- 3-- GNAT RUN-TIME COMPONENTS -- 4-- -- 5-- G N A T . H E A P _ S O R T -- 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 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; Xchg : Xchg_Procedure; Lt : Lt_Function) is 48 Max : Natural := N; 49 -- Current Max index in tree being sifted. Note that we make Max 50 -- Natural rather than Positive so that the case of sorting zero 51 -- elements is correctly handled (i.e. does nothing at all). 52 53 procedure Sift (S : Positive); 54 -- This procedure sifts up node S, i.e. converts the subtree rooted 55 -- at node S into a heap, given the precondition that any sons of 56 -- S are already heaps. 57 58 ---------- 59 -- Sift -- 60 ---------- 61 62 procedure Sift (S : Positive) is 63 C : Positive := S; 64 Son : Positive; 65 Father : Positive; 66 67 begin 68 -- This is where the optimization is done, normally we would do a 69 -- comparison at each stage between the current node and the larger 70 -- of the two sons, and continue the sift only if the current node 71 -- was less than this maximum. In this modified optimized version, 72 -- we assume that the current node will be less than the larger 73 -- son, and unconditionally sift up. Then when we get to the bottom 74 -- of the tree, we check parents to make sure that we did not make 75 -- a mistake. This roughly cuts the number of comparisons in half, 76 -- since it is almost always the case that our assumption is correct. 77 78 -- Loop to pull up larger sons 79 80 loop 81 Son := C + C; 82 83 if Son < Max then 84 if Lt (Son, Son + 1) then 85 Son := Son + 1; 86 end if; 87 elsif Son > Max then 88 exit; 89 end if; 90 91 Xchg (Son, C); 92 C := Son; 93 end loop; 94 95 -- Loop to check fathers 96 97 while C /= S loop 98 Father := C / 2; 99 100 if Lt (Father, C) then 101 Xchg (Father, C); 102 C := Father; 103 else 104 exit; 105 end if; 106 end loop; 107 end Sift; 108 109 -- Start of processing for Sort 110 111 begin 112 -- Phase one of heapsort is to build the heap. This is done by 113 -- sifting nodes N/2 .. 1 in sequence. 114 115 for J in reverse 1 .. N / 2 loop 116 Sift (J); 117 end loop; 118 119 -- In phase 2, the largest node is moved to end, reducing the size 120 -- of the tree by one, and the displaced node is sifted down from 121 -- the top, so that the largest node is again at the top. 122 123 while Max > 1 loop 124 Xchg (1, Max); 125 Max := Max - 1; 126 Sift (1); 127 end loop; 128 end Sort; 129 130end GNAT.Heap_Sort; 131