1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
-- File: SortTools.cdl
-- Created: Thu Mar 7 09:00:21 1991
-- Author: Herve Legrand
-- <hl@topsn3>
---Copyright: Matra Datavision 1991
-- 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;
---Purpose: Sort an array using the heap sort algorithm.
generic class QuickSort;
---Purpose: Sort an array using the quick sort algorithm.
generic class ShellSort;
---Purpose: Sort an array using the shell sort algorithm.
generic class StraightInsertionSort;
---Purpose: Sort an array using the straight insertion sort algorithm.
-- 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;
|
