Source code: jmat/data/arrayTools/Sort.java
1 package jmat.data.arrayTools;
2
3
4 /** Quick Sort algoritm.
5 <P>
6 Allows to sort a column quickly,
7 Using a generic version of C.A.R Hoare's Quick Sort algorithm.
8 <P>
9 */
10 public class Sort
11 {
12 //~ Instance fields ////////////////////////////////////////////////////////
13
14 /* ------------------------
15 Class variables
16 * ------------------------ */
17
18 /** Array for internal storage of the matrix to sort.
19 */
20 private double[] A;
21
22 /** Array for internal storage of the order.
23 */
24 private int[] order;
25
26 //~ Constructors ///////////////////////////////////////////////////////////
27
28 /* ------------------------
29 Constructors
30 * ------------------------ */
31
32 /** Construct an ascending order.
33 @param a Array to sort.
34 */
35 public Sort(double[] a)
36 {
37 A = a;
38 order = new int[a.length];
39
40 for (int i = 0; i < a.length; i++)
41 {
42 order[i] = i;
43 }
44
45 sort(A);
46 }
47
48 //~ Methods ////////////////////////////////////////////////////////////////
49
50 /* ------------------------
51 Public Methods
52 * ------------------------ */
53
54 /** Get the ascending order of one line.
55 @param i Line number.
56 @return Ascending order of the line.
57 */
58 public int getOrder(int i)
59 {
60 return order[i];
61 }
62
63 /* ------------------------
64 Private Methods
65 * ------------------------ */
66
67 /** This is a generic version of C.A.R Hoare's Quick Sort
68 * algorithm. This will handle arrays that are already
69 * sorted, and arrays with duplicate keys.<BR>
70 *
71 * If you think of a one dimensional array as going from
72 * the lowest index on the left to the highest index on the right
73 * then the parameters to this methodName are lowest index or
74 * left and highest index or right. The first time you call
75 * this methodName it will be with the parameters 0, a.length - 1.
76 *
77 * @param a A double array.
78 * @param lo0 Int.
79 * @param hi0 Int.
80 */
81 private void QuickSort(double[] a, int lo0, int hi0)
82 {
83 int lo = lo0;
84 int hi = hi0;
85 double mid;
86
87 if (hi0 > lo0)
88 {
89 /* Arbitrarily establishing partition element as the midpoint of
90 * the array.
91 */
92 mid = a[(lo0 + hi0) / 2];
93
94 // loop through the array until indices cross
95 while (lo <= hi)
96 {
97 /* find the first element that is greater than or equal to
98 * the partition element starting from the left Index.
99 */
100 while ((lo < hi0) && (a[lo] < mid))
101 {
102 ++lo;
103 }
104
105 /* find an element that is smaller than or equal to
106 * the partition element starting from the right Index.
107 */
108 while ((hi > lo0) && (a[hi] > mid))
109 {
110 --hi;
111 }
112
113 // if the indexes have not crossed, swap
114 if (lo <= hi)
115 {
116 swap(a, lo, hi);
117 ++lo;
118 --hi;
119 }
120 }
121
122 /* If the right index has not reached the left side of array
123 * must now sort the left partition.
124 */
125 if (lo0 < hi)
126 {
127 QuickSort(a, lo0, hi);
128 }
129
130 /* If the left index has not reached the right side of array
131 * must now sort the right partition.
132 */
133 if (lo < hi0)
134 {
135 QuickSort(a, lo, hi0);
136 }
137 }
138 }
139
140 private void sort(double[] a)
141 {
142 QuickSort(a, 0, a.length - 1);
143 }
144
145 /** Swap two positions.
146 @param a Array.
147 @param i Line number.
148 @param j Line number.
149 */
150 private void swap(double[] a, int i, int j)
151 {
152 double T;
153 T = a[i];
154 a[i] = a[j];
155 a[j] = T;
156
157 int t;
158 t = order[i];
159 order[i] = order[j];
160 order[j] = t;
161 }
162 }
163 ///////////////////////////////////////////////////////////////////////////////
164 // END OF FILE.
165 ///////////////////////////////////////////////////////////////////////////////