A.18.26 Array Sorting
1/3
{
AI95-00302-03}
{
AI05-0001-1}
The language-defined generic procedures Containers.Generic_Array_Sort, and Containers.Generic_Constrained_Array_Sort,
and Containers.Generic_Sort provide sorting
on arbitrary array types. Static Semantics
2/2
{
AI95-00302-03}
The generic library procedure Containers.Generic_Array_Sort
has the following declaration: 3/2
generic
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type range <>) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type);
pragma Pure(Ada.Containers.Generic_Array_Sort);
4/2
Reorders the elements of
Container such that the elements are sorted smallest first as determined
by the generic formal "<" operator provided. Any exception
raised during evaluation of "<" is propagated.
5/3
{
AI05-0044-1}
{
AI05-0262-1}
The actual function for the generic formal function
"<" of Generic_Array_Sort is expected to return the same
value each time it is called with a particular pair of element values.
It should define a strict weak ordering
relationship (see A.18),
that is, be irreflexive, asymmetric, and transitive;
it should not modify Container. If the actual for "<" behaves
in some other manner, the behavior of the instance of Generic_Array_Sort
is unspecified. The number of How
many times Generic_Array_Sort calls
"<" is unspecified.5.a/2
Ramification: This
implies swapping the elements, usually including an intermediate copy.
This of course means that the elements will be copied. Since the elements
are nonlimited, this usually will not be a problem. Note that there is
Implementation Advice below that the implementation should use a sort
that minimizes copying of elements.
5.b/2
The sort is not required
to be stable (and the fast algorithm required will not be stable). If
a stable sort is needed, the user can include the original location of
the element as an extra "sort key". We considered requiring
the implementation to do that, but it is mostly extra overhead -- usually
there is something already in the element that provides the needed stability.
6/2
{
AI95-00302-03}
The generic library procedure Containers.Generic_Constrained_Array_Sort
has the following declaration: 7/2
generic
type Index_Type is (<>);
type Element_Type is private;
type Array_Type is array (Index_Type) of Element_Type;
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Constrained_Array_Sort
(Container : in out Array_Type);
pragma Pure(Ada.Containers.Generic_Constrained_Array_Sort);
8/2
Reorders the elements of
Container such that the elements are sorted smallest first as determined
by the generic formal "<" operator provided. Any exception
raised during evaluation of "<" is propagated.
9/3
{
AI05-0044-1}
{
AI05-0262-1}
The actual function for the generic formal function
"<" of Generic_Constrained_Array_Sort is expected to return
the same value each time it is called with a particular pair of element
values. It should define a strict weak ordering
relationship (see A.18),
that is, be irreflexive, asymmetric, and transitive;
it should not modify Container. If the actual for "<" behaves
in some other manner, the behavior of the instance of Generic_Constrained_Array_Sort
is unspecified. The number of How
many times Generic_Constrained_Array_Sort
calls "<" is unspecified.9.1/3
{
AI05-0001-1}
The generic library procedure Containers.Generic_Sort
has the following declaration: 9.2/3
generic
type Index_Type is (<>);
with function Before (Left, Right : Index_Type) return Boolean;
with procedure Swap (Left, Right : Index_Type);
procedure Ada.Containers.Generic_Sort
(First, Last : Index_Type'Base);
pragma Pure(Ada.Containers.Generic_Sort);
9.3/3
{
AI05-0001-1}
{
AI05-0248-1}
Reorders the elements of an indexable structure,
over the range First .. Last, such that the elements are sorted in the
ordering determined by the generic formal function Before; Before should
return True if Left is to be sorted before Right. The generic formal
Before compares the elements having the given indices, and the generic
formal Swap exchanges the values of the indicated elements. Any exception
raised during evaluation of Before or Swap is propagated.9.4/3
The actual function for
the generic formal function Before of Generic_Sort is expected to return
the same value each time it is called with index values that identify
a particular pair of element values. It should define a strict weak ordering
relationship (see A.18); it should not modify
the elements. The actual function for the generic formal Swap should
exchange the values of the indicated elements. If the actual for either
Before or Swap behaves in some other manner, the behavior of Generic_Sort
is unspecified. The number of times the Generic_Sort calls Before or
Swap is unspecified.
Implementation Advice
10/2
{
AI95-00302-03}
The worst-case time complexity of a call on an
instance of Containers.Generic_Array_Sort or Containers.Generic_Constrained_Array_Sort
should be O(N**2) or better, and the average time complexity
should be better than O(N**2), where N is the length
of the Container parameter. 10.a/2
Implementation Advice:
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should have an average time complexity better than O(N**2)
and worst case no worse than O(N**2).
10.b/2
Discussion: In
other words, we're requiring the use of a sorting algorithm better than
O(N**2), such as Quicksort. No bubble sorts allowed!
11/2
{
AI95-00302-03}
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should minimize copying of elements. 11.a/2
Implementation Advice:
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should minimize copying of elements.
11.b/2
To be honest: We
do not mean “absolutely minimize” here; we're not intending
to require a single copy for each element. Rather, we want to suggest
that the sorting algorithm chosen is one that does not copy items unnecessarily.
Bubble sort would not meet this advice, for instance.
12/3
{
AI05-0248-1}
The worst-case time complexity of a call on an
instance of Containers.Generic_Sort should be O(N**2) or
better, and the average time complexity should be better than O(N**2),
where N is the difference between the Last and First parameters
plus 1. 12.a.1/3
Implementation Advice:
Containers.Generic_Sort should have
an average time complexity better than O(N**2) and worst
case no worse than O(N**2).
13/3
{
AI05-0248-1}
Containers.Generic_Sort should minimize calls to
the generic formal Swap. 13.a.1/3
Implementation Advice:
Containers.Generic_Sort should minimize
calls to the generic formal Swap.
Extensions to Ada 95
13.a/2
{
AI95-00302-03}
The generic procedures Containers.Generic_Array_Sort
and Containers.Generic_Constrained_Array_Sort are new. Extensions to Ada 2005
13.b/3
Wording Changes from Ada 2005
13.c/3
{
AI05-0044-1}
Correction: Redefined "<" actuals
to require a strict weak ordering; the old definition allowed indeterminant
comparisons that would not have worked in a sort.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
