package Utility is
--
-- Description:
-- These routines sort a list of numbers using the
-- quick sort algorithm. It returns a list of integers
-- which are the indices of the sorted numbers in ascending
-- sorted order. The original list of numbers is unchanged.
--
-- The generic packages provides two versions of the algorithm:
-- one for integers and one for float numbers. They are placed
-- in separate subpackages and are instantiated in a way
-- analogous to the Integer_io and Float_io packages.
--
-- Errors:
-- The size of the input array cannot exceed 2**64.
-- If the number of numbers to be sorted is less than 1, an
-- exception is raised. It it is 1, no sorting can occur.
--
-- Implementation details:
-- This algorithm is normally implemented by recursive calls
-- to this procedure. This implementation, instead, uses an
-- internal stack to keep track of the unsorted segments which
-- obviates the need for recursion. This seems important because
-- the recursive depth can be as many as the number of numbers
-- to be sorted.
--
-- Possible improvements:
-- For n unsorted values, this algorithm sorts in time
-- proportional to n*log(n). For n sorted values, the time
-- becomes proportional to n**2. The initial values of the
-- Order vector can be randomized to make sorted data appear
-- unsorted. See the comment below.
--
type Ivec is array (Integer range <>) of Integer;
generic
type Local_Float is digits <>;
type Dlfvec is array (Integer range <>) of Local_Float;
package Float_Sort is
procedure Qsort (Data : in Dlfvec;
Order : in out Ivec;
Length : in Natural);
end Float_Sort;
generic
type Local_Integer is range <>;
type Dlivec is array (Integer range <>) of Local_Integer;
package Integer_Sort is
procedure Qsort (Data : in Dlivec;
Order : in out Ivec;
Length : Natural);
end Integer_Sort;
end Utility;