cno1@jaguar.ucs.uofs.edu (OHARA CHRISTOPHER N) (04/24/91)
I am in search of a generic sort package. It must have the ability to
sort integers, floats, characters, and strings. I would appreciate
yuor assistance in this matter.
Thanks in advance,
CN01 - THE EAGLE -jls@rutabaga.Rational.COM (Jim Showalter) (04/25/91)
The Booch Components, from Wizard Software, include a generic sort, along with 500 other useful things. The book "Software Components With Ada", by Grady Booch (Benjamin-Cummings) describes the components and provides examples of source. You can get in touch with Wizard Software at (303) 987-1874. There are similar components available from the same source in C++. -- * "Beyond 100,000 lines of code, you should probably be coding in Ada." * * - P.G. Plauger, Convener and Secretary of the ANSI C Committee * * * * The opinions expressed herein are my own. *
rharwood@east.pima.edu (04/25/91)
In article <480@platypus.uofs.edu>, cno1@jaguar.ucs.uofs.edu (OHARA CHRISTOPHER N) writes: > > I am in search of a generic sort package. It must have the ability to > sort integers, floats, characters, and strings. I would appreciate > yuor assistance in this matter. > Thanks in advance, > CN01 - THE EAGLE - As an instructor in Pascal and Ada, I had last semester's Ada class "reconstruct" the Quicksort routine in Elliot Koffman's Pascal text, using an Ada generic package. Below are 4 files: 1) Generic package spec for SortLib 2) Generic library procedure Swap (required in SortLib package body) 3) Package body for SortLib 4) Short test procedure using array of integer. I've used this package in several of my own programs. I can't stress enough just how easy it is to maintain one's own "toolkit" of routines that are simply instantiated each time a new situation arises requiring some "generic" programming algorithm. I only wish I had more (paid) programming work to justify building a larger library. I know there must be hundreds of other sort routines out there just as good (or better than) this one, but it was so easy (took 2-3 hours of lazy midnight coding) to convert the Pascal code ("stolen" from another source) into really reusable generic Ada. ------------ generic type element is private; Type index is (<>); Type Table is array (index range <>) of element; with function ">"(L,R:element) return boolean is <>; package sortlib is procedure Sort (T : in out Table); end sortlib; ------------ generic type element is private; procedure swap (L,R: in out element); procedure swap (L,R: in out element) is Temp : Element := L; begin L := R; R := Temp; end swap; ------------ With swap; package body SortLib is --Design/algorithm after Koffman's Pascal 3rd Ed. --Section 19.8, "Quicksort". Added generics. procedure exchange is new swap (element); procedure partition(T : in out table; PivIndex: out index) is Pivot : element := t(t'first); Up, Down : Index; begin up := T'First; down := t'last; loop -- Koffman uses "<=" in the next statment -- I use "not >" so that only one -- generic formal function is required. while not (T(up) > Pivot) and then (up < t'last) loop Up := index'succ(up); end loop; while (T(down) > Pivot) loop Down := index'pred(down) ; end loop; if Up < Down then exchange(T(Up), T(Down)); end if; exit when Up >= Down; end loop; Exchange (T(T'First),T(Down)); PivIndex := Down; end partition; procedure Sort (T : in out Table) is PivIndex : index; begin if t'first < t'last then partition(T, PivIndex); Sort (T(T'first .. index'pred(PivIndex))); Sort (T(index'succ(PivIndex) .. T'last)); end if; end Sort; end SortLib; ------------ with text_io; Use text_io; with SortLib; procedure SortTest is package iio is new integer_io(integer); use iio; Type Table_type is array (integer range <>) of integer; Int_Array : Table_Type(1..5) := (4,2,76,33,19); -- Note that the 4th generic formal parameter "defaults" to the -- visible ">" function for integers. See later example for -- more complex instantiation... Package sort_anon is new sortlib(Integer, Integer, table_type); Use sort_anon; Procedure put(T : table_type) is begin for index in t'range loop put(t(index)); new_line; end loop; end put; begin put(int_array); put_line("Sorting..."); sort(Int_array); put_line("Results..."); put(int_array); end SortTest; ---------- As an additional example, suppose I wanted to store an array of employee records, generating one report by "last name/first name", another by "employee number". Here's some "code bits" for illustration: ---------- with sortlib, other_stuff; procedure Sort_Example_2 is -- Lots of details left out for brevity... -- but the important/relevant stuff is here: -- Define the "Element type" Type Employee_rec is record last_name : string(1..20); first_name : string(1..20); emp_number : integer; other_stuff : who_knows_what_else; end record; Max_Employees : constant Integer := 100; -- (or whatever) Employee_count : Integer := 0; -- Incremented as records are "read in" -- Define the "Table type" as an unconstrained array; going with -- constrained array won't work here without major rewrite. -- Also, note that index type is explicitly defined here. Type Employee_array is array (integer range <>) of integer; -- Define an appropriately large object to hold enough employees for my -- VERY small firm (yours would be larger, I hope!): Employees : Employee_array(1..max_employees); -- Define functions (bodies would have to be appropriately defined herein) -- which would return TRUE if the "key field" of the "left record" -- is greater than the "key field" of the "right record": Function greater_name (L, R : Employee_rec) return boolean; Function greater_empno (L, R : Employee_rec) return boolean; -- Now, instantiate sort routines, one for each sort key: Package sort_by_name is new sortlib(Employee_rec, Integer, Employee_array, greater_name); Package sort_by_empno is new sortlib(Employee_rec, Integer, Employee_array, greater_empno); begin Read_all_the_records_into_the_array(employees, employee_count); sort_by_name(employees(1..employee_count); Generate_report_by_name(employees(1..employee_count)); sort_by_empno(employees(1..employee_count); Generate_report_by_empno(employees(1..employee_count)); end; --------- I know this has been a bit lengthly, but the routines were already on my Mac... I just downloaded and annotated for clarity. I welcome comments, but please keep violent flames to 5 words or less per person! (It's been a rough week.) (Why do I have the feeling I've just done someone's homework?) Feel free to copy and use these routines as you desire. ----- Ray Harwood |Data Basix |Associate Faculty, Voice: (602)721-1988 |PO Box 18324 | Pima Community College FAX: (602)721-7240 |Tucson, AZ 85731 |Instructor in Ada and Pascal CompuServe: 76645,1370|AppleLink: DATA.BASIX|Internet: rharwood@east.pima.edu