135 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
136 * January 1993.
137 *
138 * <p>This implementation dumps the specified list into an array, sorts
139 * the array, and iterates over the list resetting each element
140 * from the corresponding position in the array. This avoids the
141 * n<sup>2</sup> log(n) performance that would result from attempting
142 * to sort a linked list in place.
143 *
144 * @param list the list to be sorted.
145 * @throws ClassCastException if the list contains elements that are not
146 * <i>mutually comparable</i> (for example, strings and integers).
147 * @throws UnsupportedOperationException if the specified list's
148 * list-iterator does not support the {@code set} operation.
149 * @throws IllegalArgumentException (optional) if the implementation
150 * detects that the natural ordering of the list elements is
151 * found to violate the {@link Comparable} contract
152 */
153 public static <T extends Comparable<? super T>> void sort(List<T> list) {
154 Object[] a = list.toArray();
155 Arrays.sort(a);
156 ListIterator<T> i = list.listIterator();
157 for (int j=0; j<a.length; j++) {
158 i.next();
159 i.set((T)a[j]);
160 }
161 }
162
163 /**
164 * Sorts the specified list according to the order induced by the
165 * specified comparator. All elements in the list must be <i>mutually
166 * comparable</i> using the specified comparator (that is,
167 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
168 * for any elements {@code e1} and {@code e2} in the list).
169 *
170 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
171 * not be reordered as a result of the sort.
172 *
173 * <p>The specified list must be modifiable, but need not be resizable.
174 *
197 *
198 * <p>This implementation dumps the specified list into an array, sorts
199 * the array, and iterates over the list resetting each element
200 * from the corresponding position in the array. This avoids the
201 * n<sup>2</sup> log(n) performance that would result from attempting
202 * to sort a linked list in place.
203 *
204 * @param list the list to be sorted.
205 * @param c the comparator to determine the order of the list. A
206 * {@code null} value indicates that the elements' <i>natural
207 * ordering</i> should be used.
208 * @throws ClassCastException if the list contains elements that are not
209 * <i>mutually comparable</i> using the specified comparator.
210 * @throws UnsupportedOperationException if the specified list's
211 * list-iterator does not support the {@code set} operation.
212 * @throws IllegalArgumentException (optional) if the comparator is
213 * found to violate the {@link Comparator} contract
214 */
215 public static <T> void sort(List<T> list, Comparator<? super T> c) {
216 Object[] a = list.toArray();
217 Arrays.sort(a, (Comparator)c);
218 ListIterator i = list.listIterator();
219 for (int j=0; j<a.length; j++) {
220 i.next();
221 i.set(a[j]);
222 }
223 }
224
225
226 /**
227 * Searches the specified list for the specified object using the binary
228 * search algorithm. The list must be sorted into ascending order
229 * according to the {@linkplain Comparable natural ordering} of its
230 * elements (as by the {@link #sort(List)} method) prior to making this
231 * call. If it is not sorted, the results are undefined. If the list
232 * contains multiple elements equal to the specified object, there is no
233 * guarantee which one will be found.
234 *
235 * <p>This method runs in log(n) time for a "random access" list (which
236 * provides near-constant-time positional access). If the specified list
237 * does not implement the {@link RandomAccess} interface and is large,
238 * this method will do an iterator-based binary search that performs
239 * O(n) link traversals and O(log n) element comparisons.
240 *
241 * @param list the list to be searched.
|
135 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
136 * January 1993.
137 *
138 * <p>This implementation dumps the specified list into an array, sorts
139 * the array, and iterates over the list resetting each element
140 * from the corresponding position in the array. This avoids the
141 * n<sup>2</sup> log(n) performance that would result from attempting
142 * to sort a linked list in place.
143 *
144 * @param list the list to be sorted.
145 * @throws ClassCastException if the list contains elements that are not
146 * <i>mutually comparable</i> (for example, strings and integers).
147 * @throws UnsupportedOperationException if the specified list's
148 * list-iterator does not support the {@code set} operation.
149 * @throws IllegalArgumentException (optional) if the implementation
150 * detects that the natural ordering of the list elements is
151 * found to violate the {@link Comparable} contract
152 */
153 public static <T extends Comparable<? super T>> void sort(List<T> list) {
154 Object[] a = list.toArray();
155 if(a.length <= 1) {
156 return;
157 }
158 Arrays.sort(a);
159 ListIterator<T> i = list.listIterator();
160 for (int j=0; j<a.length; j++) {
161 i.next();
162 i.set((T)a[j]);
163 }
164 }
165
166 /**
167 * Sorts the specified list according to the order induced by the
168 * specified comparator. All elements in the list must be <i>mutually
169 * comparable</i> using the specified comparator (that is,
170 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
171 * for any elements {@code e1} and {@code e2} in the list).
172 *
173 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
174 * not be reordered as a result of the sort.
175 *
176 * <p>The specified list must be modifiable, but need not be resizable.
177 *
200 *
201 * <p>This implementation dumps the specified list into an array, sorts
202 * the array, and iterates over the list resetting each element
203 * from the corresponding position in the array. This avoids the
204 * n<sup>2</sup> log(n) performance that would result from attempting
205 * to sort a linked list in place.
206 *
207 * @param list the list to be sorted.
208 * @param c the comparator to determine the order of the list. A
209 * {@code null} value indicates that the elements' <i>natural
210 * ordering</i> should be used.
211 * @throws ClassCastException if the list contains elements that are not
212 * <i>mutually comparable</i> using the specified comparator.
213 * @throws UnsupportedOperationException if the specified list's
214 * list-iterator does not support the {@code set} operation.
215 * @throws IllegalArgumentException (optional) if the comparator is
216 * found to violate the {@link Comparator} contract
217 */
218 public static <T> void sort(List<T> list, Comparator<? super T> c) {
219 Object[] a = list.toArray();
220 if(a.length <= 1) {
221 return;
222 }
223 Arrays.sort(a, (Comparator)c);
224 ListIterator<T> i = list.listIterator();
225 for (int j=0; j<a.length; j++) {
226 i.next();
227 i.set((T) a[j]);
228 }
229 }
230
231
232 /**
233 * Searches the specified list for the specified object using the binary
234 * search algorithm. The list must be sorted into ascending order
235 * according to the {@linkplain Comparable natural ordering} of its
236 * elements (as by the {@link #sort(List)} method) prior to making this
237 * call. If it is not sorted, the results are undefined. If the list
238 * contains multiple elements equal to the specified object, there is no
239 * guarantee which one will be found.
240 *
241 * <p>This method runs in log(n) time for a "random access" list (which
242 * provides near-constant-time positional access). If the specified list
243 * does not implement the {@link RandomAccess} interface and is large,
244 * this method will do an iterator-based binary search that performs
245 * O(n) link traversals and O(log n) element comparisons.
246 *
247 * @param list the list to be searched.
|