 Content-Transfer-Encoding: 7bit Sender: "Team Ada: Ada Advocacy Issues (83 & 95)" <[log in to unmask]> Subject: Re: sorting code From: Steven Deller <[log in to unmask]> Date: Tue, 19 Dec 2000 17:17:53 -0500 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Reply-To: Steven Deller <[log in to unmask]> Parts/Attachments: text/plain (244 lines) ```Jesse, One thing I missed in your original question: > ... > One of the thing I wonder about, is should I have my program > sort the whole array in one step, or have my code step thru each Letter > Prefix. If I have it go thru and just do a Letter worth at a > time, it will > almost certainly always be under 20 things to sort per letter. Because of > the small number of objects I would be sorting in this case, I'm also > considering shell sort, or insertion sort. Without a doubt you should sort the array "one letter at a time". The best algorithms are O(NlnN). Consider the following:   N NlnN N**2   2 2 4   4 8 16   8 24 64   16 64 256   ...   256 4096 65536   512 4608 262144   1024 10240 1048576 So let's say you have 256 total items, with 16 letters of 16 items each. Using an O(NlnN) algorithm, if you sort each one individually, you get 16*64 = 1024 sorting "operations", versus 4096 sorting "operations" doing the whole list. Using an O(N**2) algorithm, sort each one individually, you get 16*256 = 4096 sorting "operations", versus 65536 sorting "operations" doing the whole list. Regarding Indirect Sorting ========================== As I mentioned, the "indirect" sort may be preferable if you have large elements. After having mentioned the solution to numerous people over the years, I thought I'd take a moment or two to whip one up. It is below for anyone to use. This particular version uses the generic sorting algorithms from Rational, in its package "ordering". The spec for that package was previously emailed. The key item is the Rearrange_List procedure. WARNING: THIS IS NOT TESTED (it is compiled, and I did hand check it, but I have not had time to run the code to test its correctness). I have occasionally been known to produce faulty code that fails on execution, so beware. It should be a simple matter to change this code over to use any generic sorting code you might have. Obviously you only need one of the sorting routines. I just did all three so we had them available. As mentioned the indirect sort ensures O(N) moves of the original elements, while most sorting algorithms have O(NlnN) element moves or greater. An indirect sort can be quite a win when the original elements are large. On the negative side, indirect sort does use O(N) space, more specifically, N*4 bytes for the "indirect" array, and has the O(N) overhead of the Rearrange_List routine. The indirectsort approach has one additional benefit, namely you can create a "stable" sort from non-stable sort with just a minor change to the compare code. Without "indirection", an O(N**2) sort is needed to be "stable". The change is simply to use the following Lessthan:         function Lessthan (Left, Right : Index) return Boolean is         begin             return L (Left) < L (Right) or else                  ( L (Right) < L (Left) and Left < Right ) ;         end Lessthan; That makes equal Elements have inequality based on their index position, so position is maintained for the sort. Note that the "or else" is absolutely necessary, it can't be a simple "or". The right hand evaluation is only valid if the left is false, because "equal" is defined as neither A);     with function "<" (Left, Right : Element) return Boolean is <>; package Indirectsort is     type List is array (Index range <>) of Element;     procedure Quicksort (L : in out List);     procedure Heapsort (L : in out List);     procedure Insertionsort (L : in out List); end Indirectsort; --generic -- type Element is private; -- type Index is (<>); -- with function "<" ( left, right: Element ) return Boolean is <>; with Ordering; package body Indirectsort is -- type List is array (Index range <>) of Element;     type List_Indirect is array (Integer range <>) of Index;     procedure Rearrange_List (L : in out List; Li : in out List_Indirect) is         Temp : Element;         I, Current_Integer : Integer;         Ind, Current_Index, Next_Index : Index;         -- Index_Base is subtracted from an Index'pos value to produce         -- a corresponding Integer index into Li. It is added         -- to an Li integer index as input to Index'val to produce         -- a corresponding Index in L.         Index_Base : constant Integer := Index'Pos (L'First) - Li'First;     begin         -- The outer loop walks each list item until it finds one whose Index does not         -- match the Index of the original List. It does not check the last item         -- because, by the time it gets there, it is correct (either originally it was         -- correct, or it was changed by an ealier inner loop).         --         -- The internal loop starts with a mismatched item and walks all items in         -- a "circuit" within the list, so that only one move to Temp and then one         -- move to the final location occurs.         --         -- As the proper Element is put into the L array, the corresponding Li         -- array item is "marked" as sorted by putting the proper corresponding         -- Index value into the Li entry.         --         -- Note: The loops are O(N) even though it appears they         -- might be O(N**2). Each list element is moved at most once         -- by the sum of all executions of the inner loop.         --         Ind := L'First;         I := Li'First;         while I < Li'Last loop             -- If the correct index is not in this Li position             if Li (I) /= Ind then                 -- Current index (and integer) for rearranging are this Li position                 Current_Index := Li (I);                 Current_Integer := Index'Pos (Current_Index) - Index_Base;                 -- Put corresponding Element into Temp                 Temp := L (Current_Index);                 while Current_Integer /= I loop                     -- Get Index of next item in "circuit"                     Next_Index := Li (Current_Integer);                     -- Move proper Element into Current_Index position                     L (Current_Index) := L (Next_Index);                     -- Mark position in Li as "sorted"                     Li (Current_Integer) := Current_Index;                     -- Step to next item in "circuit"                     Current_Index := Next_Index;                     Current_Integer := Index'Pos (Current_Index) - Index_Base;                 end loop;                 -- Now store Temp into the proper element position                 L (Current_Index) := Temp;                 -- and mark this Li position as "sorted"                 Li (Current_Integer) := Current_Index;             end if;             Ind := Index'Succ (Ind);             I := Integer'Succ (I);         end loop;     end Rearrange_List; -- procedure QuickSort ( L: in out List );     procedure Quicksort (L : in out List) is         Li : List_Indirect (Integer range 0 .. L'Size - 1);         Ind : Index := L'First;         function Lessthan (Left, Right : Index) return Boolean;         package Sort is new Ordering.Quicksort (Index, Integer, Lessthan);         function Lessthan (Left, Right : Index) return Boolean is         begin             return L (Left) < L (Right);         end Lessthan;     begin         for I in Li'Range loop             Li (I) := Ind;             Ind := Index'Succ (Ind);         end loop;         Sort.Quicksort (Sort.List (Li));         Rearrange_List (L, Li);     end Quicksort; -- procedure HeapSort ( L : in out List ) ;     procedure Heapsort (L : in out List) is         Li : List_Indirect (Integer range 0 .. L'Size - 1);         Ind : Index := L'First;         function Lessthan (Left, Right : Index) return Boolean;         package Sort is new Ordering.Heapsort (Index, Integer, Lessthan);         function Lessthan (Left, Right : Index) return Boolean is         begin             return L (Left) < L (Right);         end Lessthan;     begin         for I in Li'Range loop             Li (I) := Ind;             Ind := Index'Succ (Ind);         end loop;         Sort.Heapsort (Sort.List (Li));         Rearrange_List (L, Li);     end Heapsort; -- procedure InsertionSort ( L : in out List ) :     procedure Insertionsort (L : in out List) is         Li : List_Indirect (Integer range 0 .. L'Size - 1);         Ind : Index := L'First;         function Lessthan (Left, Right : Index) return Boolean;         package Sort is new Ordering.Insertionsort (Index, Integer, Lessthan);         function Lessthan (Left, Right : Index) return Boolean is         begin             return L (Left) < L (Right);         end Lessthan;     begin         for I in Li'Range loop             Li (I) := Ind;             Ind := Index'Succ (Ind);         end loop;         Sort.Insertionsort (Sort.List (Li));         Rearrange_List (L, Li);     end Insertionsort; end Indirectsort; ```