Next: , Previous: A.18.15, Up: A.18


A.18.16 Array Sorting

1/2
The language−defined generic procedures Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort provide sorting on arbitrary array types.

Static Semantics

2/2
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/2

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 ordering relationship, 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. How many times Generic_Array_Sort calls "<" is unspecified.

6/2
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/2

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 ordering relationship, 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. How many times Generic_Constrained_Array_Sort calls "<" is unspecified.
Implementation Advice

10/2
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.

11/2
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort should minimize copying of elements.