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
6 -- This file is part of Open CASCADE Technology software library.
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.
14 -- Alternatively, this file may be used under the terms of Open CASCADE
15 -- commercial license or contractual agreement.
17 -- Revised: Fri Oct 30 1992
18 -- By : Mireille MERCIEN
23 ---Purpose: This package provides the basic sorting tools generally
30 generic class HeapSort;
31 ---Purpose: Sort an array using the heap sort algorithm.
33 generic class QuickSort;
34 ---Purpose: Sort an array using the quick sort algorithm.
36 generic class ShellSort;
37 ---Purpose: Sort an array using the shell sort algorithm.
39 generic class StraightInsertionSort;
40 ---Purpose: Sort an array using the straight insertion sort algorithm.
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.
48 ------------------------------------------------------------------------
49 -- Algorithm Stable Comparisons Moves
50 -- Min Avg Max Min Avg Max
51 ------------------------------------------------------------------------
53 -- QuickSort No nlogn nlogn n nlogn nlogn n
55 ------------------------------------------------------------------------
57 -- HeapSort No nlogn nlogn nlogn nlogn nlogn nlogn
59 ------------------------------------------------------------------------
61 -- ShellSort No - n - - n -
63 ------------------------------------------------------------------------
65 -- StraightInsertion Yes n n n n n n
67 -------------------------------------------------------------------------
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-
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).
83 ------------------------------------------------------------------------
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 );
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);
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 );
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);