src/SortTools/SortTools.cdl

   1 -- Created on: 1991-03-07
   2 -- Created by: Herve Legrand
   3 -- Copyright (c) 1991-1999 Matra Datavision
   4 -- Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 --
   6 -- This file is part of Open CASCADE Technology software library.
   7 --
   8 -- This library is free software; you can redistribute it and / or modify it
   9 -- under the terms of the GNU Lesser General Public version 2.1 as published
  10 -- by the Free Software Foundation, with special exception defined in the file
  11 -- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 -- distribution for complete text of the license and disclaimer of any warranty.
  13 --
  14 -- Alternatively, this file may be used under the terms of Open CASCADE
  15 -- commercial license or contractual agreement.
  16
  17 -- Revised:     Fri Oct 30 1992
  18 -- By     :     Mireille MERCIEN
  19
  20
  21 package SortTools
  22
  23         ---Purpose: This package provides the basic sorting tools generally
  24         --          used.
  25
  26 uses TCollection,
  27      TColStd
  28
  29 is
  30         generic class HeapSort;
  31         ---Purpose: Sort an array using the heap sort algorithm.
  32
  33         generic class QuickSort;
  34         ---Purpose: Sort an array using the quick sort algorithm.
  35
  36         generic class ShellSort;
  37         ---Purpose: Sort an array using the shell sort algorithm.
  38
  39         generic class StraightInsertionSort;
  40         ---Purpose: Sort an array using the straight insertion sort algorithm.
  41
  42
  43   -- The table below summarizes the most important characteristics that
  44   -- must be considered when selecting a particular sorting algorithm.
  45   -- A sorting algorithm is known as stable if the initial order of items
  46   -- with equals keys is preserved after the sorting operation.
  47
  48   ------------------------------------------------------------------------
  49   --  Algorithm        Stable       Comparisons            Moves
  50   --                             Min    Avg    Max    Min    Avg     Max
  51   ------------------------------------------------------------------------
  52   --                                            2                     2
  53   --  QuickSort          No     nlogn  nlogn   n      nlogn  nlogn   n
  54   --
  55   ------------------------------------------------------------------------
  56   --
  57   --  HeapSort           No     nlogn  nlogn  nlogn   nlogn  nlogn  nlogn
  58   --
  59   ------------------------------------------------------------------------
  60   --                                    1.25                   1.25
  61   --  ShellSort          No       -    n        -       -     n       -
  62   --
  63   ------------------------------------------------------------------------
  64   --                                     2     2               2      2
  65   --  StraightInsertion  Yes       n    n     n         n     n      n
  66   --
  67   -------------------------------------------------------------------------
  68
  69    --+ Heap sort exhibits an interesting time complexity, in that it runs
  70    -- on the order of nlogn for the best, average, and worst case.
  71    --+ Quick sort is still faster on the average(its constant of proportiona-
  72    -- lity is lower), but it does not guarantee such good worst-case perfor-
  73    -- mance.
  74    --+ Shell sort is not sensitive to the initial ordering and offers accepta-
  75    -- ble running time even for moderately larges arrays (say, 1000 elements).
  76    --+ Insertion sort is the method of choice for "almost sorted" arrays with
  77    -- few inversions : for such cases, it will outperform even the more
  78    -- sophisticated method (quick sort, heap sort).
  79
  80
  81 --                             Instantiations                         --
  82 --                             **************                         --
  83 ------------------------------------------------------------------------
  84
  85 --
  86 --       Instantiations QuickSort (Integer,Real)
  87 --       ***************************************
  88  class QuickSortOfInteger instantiates QuickSort(Integer,
  89                                              Array1OfInteger from TColStd,
  90                                              CompareOfInteger  from TCollection);
  91  class QuickSortOfReal instantiates QuickSort(Real,
  92                                              Array1OfReal from TColStd,
  93                                              CompareOfReal from TCollection );
  94
  95 --       Instantiations HeapSort (Integer,Real)
  96 --       ***************************************
  97  class HeapSortOfInteger instantiates HeapSort(Integer,
  98                                              Array1OfInteger from TColStd,
  99                                              CompareOfInteger  from TCollection);
 100  class HeapSortOfReal instantiates HeapSort(Real,
 101                                              Array1OfReal from TColStd,
 102                                              CompareOfReal  from TCollection);
 103
 104 --       Instantiations ShellSort (Integer,Real)
 105 --       ***************************************
 106  class ShellSortOfInteger instantiates ShellSort(Integer,
 107                                              Array1OfInteger from TColStd,
 108                                              CompareOfInteger  from TCollection);
 109  class ShellSortOfReal instantiates ShellSort(Real,
 110                                              Array1OfReal from TColStd,
 111                                              CompareOfReal from TCollection );
 112
 113 --       Instantiations StraightInsertionSort (Integer,Real)
 114 --       ***************************************************
 115  class StraightInsertionSortOfInteger instantiates
 116                            StraightInsertionSort(Integer,
 117                                              Array1OfInteger from TColStd,
 118                                              CompareOfInteger from TCollection);
 119  class StraightInsertionSortOfReal instantiates
 120                            StraightInsertionSort(Real,
 121                                              Array1OfReal from TColStd,
 122                                              CompareOfReal from TCollection);
 123
 124 end SortTools;
 125