|
111
|
1 ------------------------------------------------------------------------------
|
|
|
2 -- --
|
|
|
3 -- GNAT RUN-TIME COMPONENTS --
|
|
|
4 -- --
|
|
|
5 -- G N A T . H E A P _ S O R T _ G --
|
|
|
6 -- --
|
|
|
7 -- S p e c --
|
|
|
8 -- --
|
|
145
|
9 -- Copyright (C) 1995-2019, AdaCore --
|
|
111
|
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
|
|
|
32 -- Heapsort generic package using formal procedures
|
|
|
33
|
|
|
34 -- This package provides a generic heapsort routine that can be used with
|
|
|
35 -- different types of data.
|
|
|
36
|
|
|
37 -- See also GNAT.Heap_Sort, a version that works with subprogram access
|
|
|
38 -- parameters, allowing code sharing. The generic version is slightly more
|
|
|
39 -- efficient but does not allow code sharing and has an interface that is
|
|
|
40 -- more awkward to use.
|
|
|
41
|
|
|
42 -- There is also GNAT.Heap_Sort_A, which is now considered obsolete, but
|
|
|
43 -- was an older version working with subprogram parameters. This version
|
|
|
44 -- is retained for backwards compatibility with old versions of GNAT.
|
|
|
45
|
|
|
46 -- This heapsort algorithm uses approximately N*log(N) compares in the
|
|
|
47 -- worst case and is in place with no additional storage required. See
|
|
|
48 -- the body for exact details of the algorithm used.
|
|
|
49
|
|
|
50 generic
|
|
|
51 -- The data to be sorted is assumed to be indexed by integer values from
|
|
|
52 -- 1 to N, where N is the number of items to be sorted. In addition, the
|
|
|
53 -- index value zero is used for a temporary location used during the sort.
|
|
|
54
|
|
|
55 with procedure Move (From : Natural; To : Natural);
|
|
|
56 -- A procedure that moves the data item with index value From to the data
|
|
|
57 -- item with index value To (the old value in To being lost). An index
|
|
|
58 -- value of zero is used for moves from and to a single temporary location.
|
|
|
59 -- For best efficiency, this routine should be marked as inlined.
|
|
|
60
|
|
|
61 with function Lt (Op1, Op2 : Natural) return Boolean;
|
|
|
62 -- A function that compares two items and returns True if the item with
|
|
|
63 -- index Op1 is less than the item with Index Op2, and False if the Op1
|
|
|
64 -- item is greater than the Op2 item. If the two items are equal, then
|
|
|
65 -- it does not matter whether True or False is returned (it is slightly
|
|
|
66 -- more efficient to return False). For best efficiency, this routine
|
|
|
67 -- should be marked as inlined.
|
|
|
68
|
|
|
69 -- Note on use of temporary location
|
|
|
70
|
|
|
71 -- There are two ways of providing for the index value zero to represent
|
|
|
72 -- a temporary value. Either an extra location can be allocated at the
|
|
|
73 -- start of the array, or alternatively the Move and Lt subprograms can
|
|
|
74 -- test for the case of zero and treat it specially. In any case it is
|
|
|
75 -- desirable to specify the two subprograms as inlined and the tests for
|
|
|
76 -- zero will in this case be resolved at instantiation time.
|
|
|
77
|
|
|
78 package GNAT.Heap_Sort_G is
|
|
|
79 pragma Pure;
|
|
|
80
|
|
|
81 procedure Sort (N : Natural);
|
|
|
82 -- This procedures sorts items in the range from 1 to N into ascending
|
|
|
83 -- order making calls to Lt to do required comparisons, and Move to move
|
|
|
84 -- items around. Note that, as described above, both Move and Lt use a
|
|
|
85 -- single temporary location with index value zero. This sort is not
|
|
|
86 -- stable, i.e. the order of equal elements in the input is not preserved.
|
|
|
87
|
|
|
88 end GNAT.Heap_Sort_G;
|
