-- AdaBrowse is free software; you can redistribute it and/or modify it -- under the terms of the GNU General Public License as published by the -- Free Software Foundation; either version 2, or (at your option) any -- later version. AdaBrowse is distributed in the hope that it will be -- useful, but without any warranty; without even the implied -- warranty of merchantability or fitness for a particular purpose. -- See the GNU General Public License for more details. You should have -- received a copy of the GNU General Public License with this distribution, -- see file "GPL.txt". If not, write to the Free -- Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, -- USA. --

-- As a special exception from the GPL, if other files instantiate generics -- from this unit, or you link this unit with other files to produce an -- executable, this unit does not by itself cause the resulting executable -- to be covered by the GPL. This exception does not however invalidate any -- other reasons why the executable file might be covered by the GPL. --

-- --

-- Author:: -- Thomas Wolf (TW) --
twolf@acm.org

-- --

-- Purpose:: -- Speed and space optimized quicksort. Actually, an introspective -- quicksort with a worst-case runtime complexity of -- O (N * log2 (N)).

-- --

-- Literature:: -- Musser, D.R.: "Introspective Sorting and Selection Algorithms", -- Software -- Practice & Experience (8):983-993; 1997.

-- --

-- Tasking semantics:: -- N/A. Not abortion-safe.

-- --

-- Storage semantics:: -- No dynamic storage allocation. Stack space used is -- O (log2 (N)).

-- -- ------------------------------------------------------------------------------- pragma License (Modified_GPL); package GAL.Sorting is pragma Elaborate_Body; ---------------------------------------------------------------------------- -- A sort with a classic interface: 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 : in Element_Type) return Boolean is <>; procedure Sort_G (To_Sort : in out Array_Type); -- Sorts the array into ascending order according to the given function -- "<". This is an introspective quicksort with average *and* worst-case -- performance complexity of O(log2(N)). Stack space usage is bounded by -- log2(N). -- If To_Sort'Length >= System.Max_Int, Constraint_Error may be raised. -- (I didn't test that!) However, System.Max_Int is typically >= 2**31-1, -- and sorting arrays of 2 Gigabytes or more is not exactly a common case. ---------------------------------------------------------------------------- -- The same with an access parameter and range bounds. 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 : in Element_Type) return Boolean is <>; procedure Sort_Slice_G (To_Sort : access Array_Type; From, To : in Index_Type); -- A no-op if To_Sort'Length <= 1 or To < From. In both cases, it is -- irrelevant whether or not 'To' and 'From' are within To_Sort'Range. -- If both To_Sort'Length > 1 and From <= To, a check is made to ensure -- that both 'From' and 'To' are within To_Sort'Range, and Constraint_Error -- will be raised without modifying the array if not. Otherwise, the given -- slice To_Sort (From .. To) is sorted into ascending order according to -- '<'. ---------------------------------------------------------------------------- -- A very general sort that can be used to sort whatever you like. As -- long as you can provide random access in constant time, this will -- be a logarithmic sort. (It's an introspective quicksort, too.) generic with function Is_Smaller (Left, Right : in Integer) return Boolean; -- Shall return True if the element at index 'Left' is smaller than -- the element at index 'Right' and Fasle otherwise. with procedure Copy (To, From : in Integer); -- Shall copy the element at index 'From' to position 'To'. procedure Sort_Indexed_G (Left, Right : in Natural); -- Sorts range Left .. Right of your data by calling 'Is_Smaller' for -- comparisons and 'Move' to move elements around. Both 'Is_Smaller' -- and 'Move' must be prepared to receive indices -1 and -2, which denote -- two single (and different) temporary locations. Both routines are never -- called with both indices negative, one index at least is always -- in the (Left .. Right). ---------------------------------------------------------------------------- -- Same as above, but using access-to-subroutines. type Comparator is access function (Left, Right : in Integer) return Boolean; type Copier is access procedure (To, From : in Integer); procedure Sort (Left, Right : in Natural; Is_Smaller : in Comparator; Copy : in Copier); -- Of course, both 'Is_Smaller' and 'Copy' must not be null or this will -- raise Constraint_Error! ---------------------------------------------------------------------------- end GAL.Sorting;