+++ /dev/null
--- Created on: 1991-03-07
--- Created by: Herve Legrand
--- Copyright (c) 1991-1999 Matra Datavision
--- Copyright (c) 1999-2014 OPEN CASCADE SAS
---
--- This file is part of Open CASCADE Technology software library.
---
--- This library is free software; you can redistribute it and/or modify it under
--- the terms of the GNU Lesser General Public License version 2.1 as published
--- by the Free Software Foundation, with special exception defined in the file
--- OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
--- distribution for complete text of the license and disclaimer of any warranty.
---
--- Alternatively, this file may be used under the terms of Open CASCADE
--- commercial license or contractual agreement.
-
--- Revised: Fri Oct 30 1992
--- By : Mireille MERCIEN
-
-
-package SortTools
-
- ---Purpose: This package provides the basic sorting tools generally
- -- used.
-
-uses TCollection,
- TColStd
-
-is
- generic class HeapSort;
-
- generic class QuickSort;
-
- generic class ShellSort;
-
- generic class StraightInsertionSort;
-
-
- -- The table below summarizes the most important characteristics that
- -- must be considered when selecting a particular sorting algorithm.
- -- A sorting algorithm is known as stable if the initial order of items
- -- with equals keys is preserved after the sorting operation.
-
- ------------------------------------------------------------------------
- -- Algorithm Stable Comparisons Moves
- -- Min Avg Max Min Avg Max
- ------------------------------------------------------------------------
- -- 2 2
- -- QuickSort No nlogn nlogn n nlogn nlogn n
- --
- ------------------------------------------------------------------------
- --
- -- HeapSort No nlogn nlogn nlogn nlogn nlogn nlogn
- --
- ------------------------------------------------------------------------
- -- 1.25 1.25
- -- ShellSort No - n - - n -
- --
- ------------------------------------------------------------------------
- -- 2 2 2 2
- -- StraightInsertion Yes n n n n n n
- --
- -------------------------------------------------------------------------
-
- --+ Heap sort exhibits an interesting time complexity, in that it runs
- -- on the order of nlogn for the best, average, and worst case.
- --+ Quick sort is still faster on the average(its constant of proportiona-
- -- lity is lower), but it does not guarantee such good worst-case perfor-
- -- mance.
- --+ Shell sort is not sensitive to the initial ordering and offers accepta-
- -- ble running time even for moderately larges arrays (say, 1000 elements).
- --+ Insertion sort is the method of choice for "almost sorted" arrays with
- -- few inversions : for such cases, it will outperform even the more
- -- sophisticated method (quick sort, heap sort).
-
-
--- Instantiations --
--- ************** --
-------------------------------------------------------------------------
-
---
--- Instantiations QuickSort (Integer,Real)
--- ***************************************
- class QuickSortOfInteger instantiates QuickSort(Integer,
- Array1OfInteger from TColStd,
- CompareOfInteger from TCollection);
- class QuickSortOfReal instantiates QuickSort(Real,
- Array1OfReal from TColStd,
- CompareOfReal from TCollection );
-
--- Instantiations HeapSort (Integer,Real)
--- ***************************************
- class HeapSortOfInteger instantiates HeapSort(Integer,
- Array1OfInteger from TColStd,
- CompareOfInteger from TCollection);
- class HeapSortOfReal instantiates HeapSort(Real,
- Array1OfReal from TColStd,
- CompareOfReal from TCollection);
-
--- Instantiations ShellSort (Integer,Real)
--- ***************************************
- class ShellSortOfInteger instantiates ShellSort(Integer,
- Array1OfInteger from TColStd,
- CompareOfInteger from TCollection);
- class ShellSortOfReal instantiates ShellSort(Real,
- Array1OfReal from TColStd,
- CompareOfReal from TCollection );
-
--- Instantiations StraightInsertionSort (Integer,Real)
--- ***************************************************
- class StraightInsertionSortOfInteger instantiates
- StraightInsertionSort(Integer,
- Array1OfInteger from TColStd,
- CompareOfInteger from TCollection);
- class StraightInsertionSortOfReal instantiates
- StraightInsertionSort(Real,
- Array1OfReal from TColStd,
- CompareOfReal from TCollection);
-
-end SortTools;
-