1 //******************************************************************************
2 //
3 // File: Sorting.java
4 // Package: edu.rit.util
5 // Unit: Class edu.rit.util.Sorting
6 //
7 // This Java source file is copyright (C) 2011 by Alan Kaminsky. All rights
8 // reserved. For further information, contact the author, Alan Kaminsky, at
9 // ark@cs.rit.edu.
10 //
11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12 // software; you can redistribute it and/or modify it under the terms of the GNU
13 // General Public License as published by the Free Software Foundation; either
14 // version 3 of the License, or (at your option) any later version.
15 //
16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19 //
20 // Linking this library statically or dynamically with other modules is making a
21 // combined work based on this library. Thus, the terms and conditions of the GNU
22 // General Public License cover the whole combination.
23 //
24 // As a special exception, the copyright holders of this library give you
25 // permission to link this library with independent modules to produce an
26 // executable, regardless of the license terms of these independent modules, and
27 // to copy and distribute the resulting executable under terms of your choice,
28 // provided that you also meet, for each linked independent module, the terms
29 // and conditions of the license of that module. An independent module is a module
30 // which is not derived from or based on this library. If you modify this library,
31 // you may extend this exception to your version of the library, but you are not
32 // obligated to do so. If you do not wish to do so, delete this exception
33 // statement from your version.
34 //
35 // A copy of the GNU General Public License is provided in the file gpl.txt. You
36 // may also obtain a copy of the GNU General Public License on the World Wide
37 // Web at http://www.gnu.org/licenses/gpl.html.
38 //
39 //******************************************************************************
40 package edu.rit.util;
41
42 /**
43 * Class Sorting provides static methods for sorting arrays of primitive types
44 * and object types.
45 * <P>
46 * <I>Note:</I> The operations in class Sorting are not multiple thread safe.
47 *
48 * @author Alan Kaminsky
49 * @version 02-Nov-2011
50 */
51 public class Sorting {
52
53 // Prevent construction.
54 private Sorting() {
55 }
56
57 // Exported helper classes.
58 /**
59 * Class Sorting.Byte is the base class for a helper object used to sort an
60 * array of type <code>byte[]</code>.
61 *
62 * @author Alan Kaminsky
63 * @version 20-Oct-2010
64 */
65 public static class Byte {
66
67 /**
68 * Compare two elements in the given array. This determines the order of
69 * the elements in the sorted array.
70 * <P>
71 * The default implementation returns true if <code>x[a] < x[b]</code>,
72 * which sorts the array into ascending order. A subclass can override
73 * this method to obtain a different ordering criterion; for example,
74 * descending order.
75 *
76 * @param x Array being sorted.
77 * @param a Index of first array element being compared.
78 * @param b Index of second array element being compared.
79 *
80 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
81 * desired ordering, false otherwise.
82 */
83 public boolean comesBefore(byte[] x,
84 int a,
85 int b) {
86 return x[a] < x[b];
87 }
88
89 /**
90 * Swap two elements in the given array.
91 * <P>
92 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
93 * subclass can override this method to do something different; for
94 * example, to swap the elements of other arrays in addition to
95 * <code>x</code>.
96 *
97 * @param x Array being sorted.
98 * @param a Index of first array element being swapped.
99 * @param b Index of second array element being swapped.
100 */
101 public void swap(byte[] x,
102 int a,
103 int b) {
104 byte t = x[a];
105 x[a] = x[b];
106 x[b] = t;
107 }
108 }
109
110 /**
111 * Class Sorting.Character is the base class for a helper object used to
112 * sort an array of type <code>char[]</code>.
113 *
114 * @author Alan Kaminsky
115 * @version 20-Oct-2010
116 */
117 public static class Character {
118
119 /**
120 * Compare two elements in the given array. This determines the order of
121 * the elements in the sorted array.
122 * <P>
123 * The default implementation returns true if <code>x[a] < x[b]</code>,
124 * which sorts the array into ascending order. A subclass can override
125 * this method to obtain a different ordering criterion; for example,
126 * descending order.
127 *
128 * @param x Array being sorted.
129 * @param a Index of first array element being compared.
130 * @param b Index of second array element being compared.
131 *
132 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
133 * desired ordering, false otherwise.
134 */
135 public boolean comesBefore(char[] x,
136 int a,
137 int b) {
138 return x[a] < x[b];
139 }
140
141 /**
142 * Swap two elements in the given array.
143 * <P>
144 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
145 * subclass can override this method to do something different; for
146 * example, to swap the elements of other arrays in addition to
147 * <code>x</code>.
148 *
149 * @param x Array being sorted.
150 * @param a Index of first array element being swapped.
151 * @param b Index of second array element being swapped.
152 */
153 public void swap(char[] x,
154 int a,
155 int b) {
156 char t = x[a];
157 x[a] = x[b];
158 x[b] = t;
159 }
160 }
161
162 /**
163 * Class Sorting.Short is the base class for a helper object used to sort an
164 * array of type <code>short[]</code>.
165 *
166 * @author Alan Kaminsky
167 * @version 20-Oct-2010
168 */
169 public static class Short {
170
171 /**
172 * Compare two elements in the given array. This determines the order of
173 * the elements in the sorted array.
174 * <P>
175 * The default implementation returns true if <code>x[a] < x[b]</code>,
176 * which sorts the array into ascending order. A subclass can override
177 * this method to obtain a different ordering criterion; for example,
178 * descending order.
179 *
180 * @param x Array being sorted.
181 * @param a Index of first array element being compared.
182 * @param b Index of second array element being compared.
183 *
184 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
185 * desired ordering, false otherwise.
186 */
187 public boolean comesBefore(short[] x,
188 int a,
189 int b) {
190 return x[a] < x[b];
191 }
192
193 /**
194 * Swap two elements in the given array.
195 * <P>
196 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
197 * subclass can override this method to do something different; for
198 * example, to swap the elements of other arrays in addition to
199 * <code>x</code>.
200 *
201 * @param x Array being sorted.
202 * @param a Index of first array element being swapped.
203 * @param b Index of second array element being swapped.
204 */
205 public void swap(short[] x,
206 int a,
207 int b) {
208 short t = x[a];
209 x[a] = x[b];
210 x[b] = t;
211 }
212 }
213
214 /**
215 * Class Sorting.Integer is the base class for a helper object used to sort
216 * an array of type <code>int[]</code>.
217 *
218 * @author Alan Kaminsky
219 * @version 20-Oct-2010
220 */
221 public static class Integer {
222
223 /**
224 * Compare two elements in the given array. This determines the order of
225 * the elements in the sorted array.
226 * <P>
227 * The default implementation returns true if <code>x[a] < x[b]</code>,
228 * which sorts the array into ascending order. A subclass can override
229 * this method to obtain a different ordering criterion; for example,
230 * descending order.
231 *
232 * @param x Array being sorted.
233 * @param a Index of first array element being compared.
234 * @param b Index of second array element being compared.
235 *
236 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
237 * desired ordering, false otherwise.
238 */
239 public boolean comesBefore(int[] x,
240 int a,
241 int b) {
242 return x[a] < x[b];
243 }
244
245 /**
246 * Swap two elements in the given array.
247 * <P>
248 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
249 * subclass can override this method to do something different; for
250 * example, to swap the elements of other arrays in addition to
251 * <code>x</code>.
252 *
253 * @param x Array being sorted.
254 * @param a Index of first array element being swapped.
255 * @param b Index of second array element being swapped.
256 */
257 public void swap(int[] x,
258 int a,
259 int b) {
260 int t = x[a];
261 x[a] = x[b];
262 x[b] = t;
263 }
264 }
265
266 /**
267 * Class Sorting.Long is the base class for a helper object used to sort an
268 * array of type <code>long[]</code>.
269 *
270 * @author Alan Kaminsky
271 * @version 20-Oct-2010
272 */
273 public static class Long {
274
275 /**
276 * Compare two elements in the given array. This determines the order of
277 * the elements in the sorted array.
278 * <P>
279 * The default implementation returns true if <code>x[a] < x[b]</code>,
280 * which sorts the array into ascending order. A subclass can override
281 * this method to obtain a different ordering criterion; for example,
282 * descending order.
283 *
284 * @param x Array being sorted.
285 * @param a Index of first array element being compared.
286 * @param b Index of second array element being compared.
287 *
288 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
289 * desired ordering, false otherwise.
290 */
291 public boolean comesBefore(long[] x,
292 int a,
293 int b) {
294 return x[a] < x[b];
295 }
296
297 /**
298 * Swap two elements in the given array.
299 * <P>
300 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
301 * subclass can override this method to do something different; for
302 * example, to swap the elements of other arrays in addition to
303 * <code>x</code>.
304 *
305 * @param x Array being sorted.
306 * @param a Index of first array element being swapped.
307 * @param b Index of second array element being swapped.
308 */
309 public void swap(long[] x,
310 int a,
311 int b) {
312 long t = x[a];
313 x[a] = x[b];
314 x[b] = t;
315 }
316 }
317
318 /**
319 * Class Sorting.Float is the base class for a helper object used to sort an
320 * array of type <code>float[]</code>.
321 *
322 * @author Alan Kaminsky
323 * @version 20-Oct-2010
324 */
325 public static class Float {
326
327 /**
328 * Compare two elements in the given array. This determines the order of
329 * the elements in the sorted array.
330 * <P>
331 * The default implementation returns true if <code>x[a] < x[b]</code>,
332 * which sorts the array into ascending order. A subclass can override
333 * this method to obtain a different ordering criterion; for example,
334 * descending order.
335 *
336 * @param x Array being sorted.
337 * @param a Index of first array element being compared.
338 * @param b Index of second array element being compared.
339 *
340 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
341 * desired ordering, false otherwise.
342 */
343 public boolean comesBefore(float[] x,
344 int a,
345 int b) {
346 return x[a] < x[b];
347 }
348
349 /**
350 * Swap two elements in the given array.
351 * <P>
352 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
353 * subclass can override this method to do something different; for
354 * example, to swap the elements of other arrays in addition to
355 * <code>x</code>.
356 *
357 * @param x Array being sorted.
358 * @param a Index of first array element being swapped.
359 * @param b Index of second array element being swapped.
360 */
361 public void swap(float[] x,
362 int a,
363 int b) {
364 float t = x[a];
365 x[a] = x[b];
366 x[b] = t;
367 }
368 }
369
370 /**
371 * Class Sorting.Double is the base class for a helper object used to sort
372 * an array of type <code>double[]</code>.
373 *
374 * @author Alan Kaminsky
375 * @version 20-Oct-2010
376 */
377 public static class Double {
378
379 /**
380 * Compare two elements in the given array. This determines the order of
381 * the elements in the sorted array.
382 * <P>
383 * The default implementation returns true if <code>x[a] < x[b]</code>,
384 * which sorts the array into ascending order. A subclass can override
385 * this method to obtain a different ordering criterion; for example,
386 * descending order.
387 *
388 * @param x Array being sorted.
389 * @param a Index of first array element being compared.
390 * @param b Index of second array element being compared.
391 *
392 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
393 * desired ordering, false otherwise.
394 */
395 public boolean comesBefore(double[] x,
396 int a,
397 int b) {
398 return x[a] < x[b];
399 }
400
401 /**
402 * Swap two elements in the given array.
403 * <P>
404 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
405 * subclass can override this method to do something different; for
406 * example, to swap the elements of other arrays in addition to
407 * <code>x</code>.
408 *
409 * @param x Array being sorted.
410 * @param a Index of first array element being swapped.
411 * @param b Index of second array element being swapped.
412 */
413 public void swap(double[] x,
414 int a,
415 int b) {
416 double t = x[a];
417 x[a] = x[b];
418 x[b] = t;
419 }
420 }
421
422 /**
423 * Class Sorting.Object is the abstract base class for a helper object used
424 * to sort an array of objects of type <code>T[]</code>.
425 *
426 * @param <T> Data type of the array elements.
427 *
428 * @author Alan Kaminsky
429 * @version 20-Oct-2010
430 */
431 public static abstract class Object<T> {
432
433 /**
434 * Compare two elements in the given array. This determines the order of
435 * the elements in the sorted array.
436 *
437 * @param x Array being sorted.
438 * @param a Index of first array element being compared.
439 * @param b Index of second array element being compared.
440 *
441 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the
442 * desired ordering, false otherwise.
443 */
444 public abstract boolean comesBefore(T[] x,
445 int a,
446 int b);
447
448 /**
449 * Swap two elements in the given array.
450 * <P>
451 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A
452 * subclass can override this method to do something different; for
453 * example, to swap the elements of other arrays in addition to
454 * <code>x</code>.
455 *
456 * @param x Array being sorted.
457 * @param a Index of first array element being swapped.
458 * @param b Index of second array element being swapped.
459 */
460 public void swap(T[] x,
461 int a,
462 int b) {
463 T t = x[a];
464 x[a] = x[b];
465 x[b] = t;
466 }
467 }
468
469 // Exported operations.
470 /**
471 * Sort the given array of type <code>byte[]</code>. The given helper object is
472 * used to determine the desired ordering of the array elements and to swap
473 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
474 * algorithm is used.
475 *
476 * @param x Array to be sorted.
477 * @param helper Helper object.
478 * @return The array that was sorted (<code>x</code>).
479 */
480 public static byte[] sort(byte[] x,
481 Sorting.Byte helper) {
482 int n = x.length;
483 for (int i = 2; i <= n; ++i) {
484 siftUp(x, i, helper);
485 }
486 for (int i = n; i >= 2; --i) {
487 helper.swap(x, 0, i - 1);
488 siftDown(x, i - 1, helper);
489 }
490 return x;
491 }
492
493 private static void siftUp(byte[] x,
494 int c, // 1-based index
495 Sorting.Byte helper) {
496 int p = c >> 1; // 1-based index
497 while (p >= 1) {
498 if (helper.comesBefore(x, p - 1, c - 1)) {
499 helper.swap(x, p - 1, c - 1);
500 } else {
501 break;
502 }
503 c = p;
504 p = c >> 1;
505 }
506 }
507
508 private static void siftDown(byte[] x,
509 int n, // 1-based index
510 Sorting.Byte helper) {
511 int p = 1; // 1-based index
512 int ca = 2; // 1-based index
513 int cb = 3; // 1-based index
514 while (ca <= n) {
515 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
516 if (helper.comesBefore(x, p - 1, cb - 1)) {
517 helper.swap(x, p - 1, cb - 1);
518 p = cb;
519 } else {
520 break;
521 }
522 } else {
523 if (helper.comesBefore(x, p - 1, ca - 1)) {
524 helper.swap(x, p - 1, ca - 1);
525 p = ca;
526 } else {
527 break;
528 }
529 }
530 ca = p << 1;
531 cb = ca + 1;
532 }
533 }
534
535 /**
536 * Sort the given array of type <code>char[]</code>. The given helper object is
537 * used to determine the desired ordering of the array elements and to swap
538 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
539 * algorithm is used.
540 *
541 * @param x Array to be sorted.
542 * @param helper Helper object.
543 * @return The array that was sorted (<code>x</code>).
544 */
545 public static char[] sort(char[] x,
546 Sorting.Character helper) {
547 int n = x.length;
548 for (int i = 2; i <= n; ++i) {
549 siftUp(x, i, helper);
550 }
551 for (int i = n; i >= 2; --i) {
552 helper.swap(x, 0, i - 1);
553 siftDown(x, i - 1, helper);
554 }
555 return x;
556 }
557
558 private static void siftUp(char[] x,
559 int c, // 1-based index
560 Sorting.Character helper) {
561 int p = c >> 1; // 1-based index
562 while (p >= 1) {
563 if (helper.comesBefore(x, p - 1, c - 1)) {
564 helper.swap(x, p - 1, c - 1);
565 } else {
566 break;
567 }
568 c = p;
569 p = c >> 1;
570 }
571 }
572
573 private static void siftDown(char[] x,
574 int n, // 1-based index
575 Sorting.Character helper) {
576 int p = 1; // 1-based index
577 int ca = 2; // 1-based index
578 int cb = 3; // 1-based index
579 while (ca <= n) {
580 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
581 if (helper.comesBefore(x, p - 1, cb - 1)) {
582 helper.swap(x, p - 1, cb - 1);
583 p = cb;
584 } else {
585 break;
586 }
587 } else {
588 if (helper.comesBefore(x, p - 1, ca - 1)) {
589 helper.swap(x, p - 1, ca - 1);
590 p = ca;
591 } else {
592 break;
593 }
594 }
595 ca = p << 1;
596 cb = ca + 1;
597 }
598 }
599
600 /**
601 * Sort the given array of type <code>short[]</code>. The given helper object is
602 * used to determine the desired ordering of the array elements and to swap
603 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
604 * algorithm is used.
605 *
606 * @param x Array to be sorted.
607 * @param helper Helper object.
608 * @return The array that was sorted (<code>x</code>).
609 */
610 public static short[] sort(short[] x,
611 Sorting.Short helper) {
612 int n = x.length;
613 for (int i = 2; i <= n; ++i) {
614 siftUp(x, i, helper);
615 }
616 for (int i = n; i >= 2; --i) {
617 helper.swap(x, 0, i - 1);
618 siftDown(x, i - 1, helper);
619 }
620 return x;
621 }
622
623 private static void siftUp(short[] x,
624 int c, // 1-based index
625 Sorting.Short helper) {
626 int p = c >> 1; // 1-based index
627 while (p >= 1) {
628 if (helper.comesBefore(x, p - 1, c - 1)) {
629 helper.swap(x, p - 1, c - 1);
630 } else {
631 break;
632 }
633 c = p;
634 p = c >> 1;
635 }
636 }
637
638 private static void siftDown(short[] x,
639 int n, // 1-based index
640 Sorting.Short helper) {
641 int p = 1; // 1-based index
642 int ca = 2; // 1-based index
643 int cb = 3; // 1-based index
644 while (ca <= n) {
645 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
646 if (helper.comesBefore(x, p - 1, cb - 1)) {
647 helper.swap(x, p - 1, cb - 1);
648 p = cb;
649 } else {
650 break;
651 }
652 } else {
653 if (helper.comesBefore(x, p - 1, ca - 1)) {
654 helper.swap(x, p - 1, ca - 1);
655 p = ca;
656 } else {
657 break;
658 }
659 }
660 ca = p << 1;
661 cb = ca + 1;
662 }
663 }
664
665 /**
666 * Sort the given array of type <code>int[]</code>. The given helper object is
667 * used to determine the desired ordering of the array elements and to swap
668 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
669 * algorithm is used.
670 *
671 * @param x Array to be sorted.
672 * @param helper Helper object.
673 * @return The array that was sorted (<code>x</code>).
674 */
675 public static int[] sort(int[] x,
676 Sorting.Integer helper) {
677 int n = x.length;
678 for (int i = 2; i <= n; ++i) {
679 siftUp(x, i, helper);
680 }
681 for (int i = n; i >= 2; --i) {
682 helper.swap(x, 0, i - 1);
683 siftDown(x, i - 1, helper);
684 }
685 return x;
686 }
687
688 private static void siftUp(int[] x,
689 int c, // 1-based index
690 Sorting.Integer helper) {
691 int p = c >> 1; // 1-based index
692 while (p >= 1) {
693 if (helper.comesBefore(x, p - 1, c - 1)) {
694 helper.swap(x, p - 1, c - 1);
695 } else {
696 break;
697 }
698 c = p;
699 p = c >> 1;
700 }
701 }
702
703 private static void siftDown(int[] x,
704 int n, // 1-based index
705 Sorting.Integer helper) {
706 int p = 1; // 1-based index
707 int ca = 2; // 1-based index
708 int cb = 3; // 1-based index
709 while (ca <= n) {
710 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
711 if (helper.comesBefore(x, p - 1, cb - 1)) {
712 helper.swap(x, p - 1, cb - 1);
713 p = cb;
714 } else {
715 break;
716 }
717 } else {
718 if (helper.comesBefore(x, p - 1, ca - 1)) {
719 helper.swap(x, p - 1, ca - 1);
720 p = ca;
721 } else {
722 break;
723 }
724 }
725 ca = p << 1;
726 cb = ca + 1;
727 }
728 }
729
730 /**
731 * Sort the given array of type <code>long[]</code>. The given helper object is
732 * used to determine the desired ordering of the array elements and to swap
733 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
734 * algorithm is used.
735 *
736 * @param x Array to be sorted.
737 * @param helper Helper object.
738 * @return The array that was sorted (<code>x</code>).
739 */
740 public static long[] sort(long[] x,
741 Sorting.Long helper) {
742 int n = x.length;
743 for (int i = 2; i <= n; ++i) {
744 siftUp(x, i, helper);
745 }
746 for (int i = n; i >= 2; --i) {
747 helper.swap(x, 0, i - 1);
748 siftDown(x, i - 1, helper);
749 }
750 return x;
751 }
752
753 private static void siftUp(long[] x,
754 int c, // 1-based index
755 Sorting.Long helper) {
756 int p = c >> 1; // 1-based index
757 while (p >= 1) {
758 if (helper.comesBefore(x, p - 1, c - 1)) {
759 helper.swap(x, p - 1, c - 1);
760 } else {
761 break;
762 }
763 c = p;
764 p = c >> 1;
765 }
766 }
767
768 private static void siftDown(long[] x,
769 int n, // 1-based index
770 Sorting.Long helper) {
771 int p = 1; // 1-based index
772 int ca = 2; // 1-based index
773 int cb = 3; // 1-based index
774 while (ca <= n) {
775 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
776 if (helper.comesBefore(x, p - 1, cb - 1)) {
777 helper.swap(x, p - 1, cb - 1);
778 p = cb;
779 } else {
780 break;
781 }
782 } else {
783 if (helper.comesBefore(x, p - 1, ca - 1)) {
784 helper.swap(x, p - 1, ca - 1);
785 p = ca;
786 } else {
787 break;
788 }
789 }
790 ca = p << 1;
791 cb = ca + 1;
792 }
793 }
794
795 /**
796 * Sort the given array of type <code>float[]</code>. The given helper object is
797 * used to determine the desired ordering of the array elements and to swap
798 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort
799 * algorithm is used.
800 *
801 * @param x Array to be sorted.
802 * @param helper Helper object.
803 * @return The array that was sorted (<code>x</code>).
804 */
805 public static float[] sort(float[] x,
806 Sorting.Float helper) {
807 int n = x.length;
808 for (int i = 2; i <= n; ++i) {
809 siftUp(x, i, helper);
810 }
811 for (int i = n; i >= 2; --i) {
812 helper.swap(x, 0, i - 1);
813 siftDown(x, i - 1, helper);
814 }
815 return x;
816 }
817
818 private static void siftUp(float[] x,
819 int c, // 1-based index
820 Sorting.Float helper) {
821 int p = c >> 1; // 1-based index
822 while (p >= 1) {
823 if (helper.comesBefore(x, p - 1, c - 1)) {
824 helper.swap(x, p - 1, c - 1);
825 } else {
826 break;
827 }
828 c = p;
829 p = c >> 1;
830 }
831 }
832
833 private static void siftDown(float[] x,
834 int n, // 1-based index
835 Sorting.Float helper) {
836 int p = 1; // 1-based index
837 int ca = 2; // 1-based index
838 int cb = 3; // 1-based index
839 while (ca <= n) {
840 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
841 if (helper.comesBefore(x, p - 1, cb - 1)) {
842 helper.swap(x, p - 1, cb - 1);
843 p = cb;
844 } else {
845 break;
846 }
847 } else {
848 if (helper.comesBefore(x, p - 1, ca - 1)) {
849 helper.swap(x, p - 1, ca - 1);
850 p = ca;
851 } else {
852 break;
853 }
854 }
855 ca = p << 1;
856 cb = ca + 1;
857 }
858 }
859
860 /**
861 * Sort the given array of type <code>double[]</code>. The given helper object
862 * is used to determine the desired ordering of the array elements and to
863 * swap the array elements. An <I>O</I>(<I>n</I> log <I>n</I>)
864 * heapsort algorithm is used.
865 *
866 * @param x Array to be sorted.
867 * @param helper Helper object.
868 * @return The array that was sorted (<code>x</code>).
869 */
870 public static double[] sort(double[] x,
871 Sorting.Double helper) {
872 int n = x.length;
873 for (int i = 2; i <= n; ++i) {
874 siftUp(x, i, helper);
875 }
876 for (int i = n; i >= 2; --i) {
877 helper.swap(x, 0, i - 1);
878 siftDown(x, i - 1, helper);
879 }
880 return x;
881 }
882
883 private static void siftUp(double[] x,
884 int c, // 1-based index
885 Sorting.Double helper) {
886 int p = c >> 1; // 1-based index
887 while (p >= 1) {
888 if (helper.comesBefore(x, p - 1, c - 1)) {
889 helper.swap(x, p - 1, c - 1);
890 } else {
891 break;
892 }
893 c = p;
894 p = c >> 1;
895 }
896 }
897
898 private static void siftDown(double[] x,
899 int n, // 1-based index
900 Sorting.Double helper) {
901 int p = 1; // 1-based index
902 int ca = 2; // 1-based index
903 int cb = 3; // 1-based index
904 while (ca <= n) {
905 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
906 if (helper.comesBefore(x, p - 1, cb - 1)) {
907 helper.swap(x, p - 1, cb - 1);
908 p = cb;
909 } else {
910 break;
911 }
912 } else {
913 if (helper.comesBefore(x, p - 1, ca - 1)) {
914 helper.swap(x, p - 1, ca - 1);
915 p = ca;
916 } else {
917 break;
918 }
919 }
920 ca = p << 1;
921 cb = ca + 1;
922 }
923 }
924
925 /**
926 * Sort the given object array of type <code>T[]</code>. The given helper object
927 * is used to determine the desired ordering of the array elements and to
928 * swap the array elements. An <I>O</I>(<I>n</I> log <I>n</I>)
929 * heapsort algorithm is used.
930 *
931 * @param <T> Data type of the array elements.
932 * @param x Array to be sorted.
933 * @param helper Helper object.
934 * @return The array that was sorted (<code>x</code>).
935 */
936 public static <T> T[] sort(T[] x,
937 Sorting.Object<T> helper) {
938 int n = x.length;
939 for (int i = 2; i <= n; ++i) {
940 siftUp(x, i, helper);
941 }
942 for (int i = n; i >= 2; --i) {
943 helper.swap(x, 0, i - 1);
944 siftDown(x, i - 1, helper);
945 }
946 return x;
947 }
948
949 private static <T> void siftUp(T[] x,
950 int c, // 1-based index
951 Sorting.Object<T> helper) {
952 int p = c >> 1; // 1-based index
953 while (p >= 1) {
954 if (helper.comesBefore(x, p - 1, c - 1)) {
955 helper.swap(x, p - 1, c - 1);
956 } else {
957 break;
958 }
959 c = p;
960 p = c >> 1;
961 }
962 }
963
964 private static <T> void siftDown(T[] x,
965 int n, // 1-based index
966 Sorting.Object<T> helper) {
967 int p = 1; // 1-based index
968 int ca = 2; // 1-based index
969 int cb = 3; // 1-based index
970 while (ca <= n) {
971 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) {
972 if (helper.comesBefore(x, p - 1, cb - 1)) {
973 helper.swap(x, p - 1, cb - 1);
974 p = cb;
975 } else {
976 break;
977 }
978 } else {
979 if (helper.comesBefore(x, p - 1, ca - 1)) {
980 helper.swap(x, p - 1, ca - 1);
981 p = ca;
982 } else {
983 break;
984 }
985 }
986 ca = p << 1;
987 cb = ca + 1;
988 }
989 }
990
991 // Unit test main program.
992 // /**
993 // * Unit test main program.
994 // * <P>
995 // * Usage: java edu.rit.util.Sorting <I>n</I> <I>seed</I>
996 // * <BR><I>n</I> = Array length
997 // * <BR><I>seed</I> = Random seed
998 // */
999 // public static void main
1000 // (String[] args)
1001 // {
1002 // if (args.length != 2) usage();
1003 // int n = java.lang.Integer.parseInt (args[0]);
1004 // long seed = java.lang.Long.parseLong (args[1]);
1005 // byte[] x = new byte [n];
1006 // Random prng = Random.getInstance (seed);
1007 // for (int i = 0; i < n; ++ i) x[i] = prng.nextByte();
1008 // for (int i = 0; i < n; ++ i) System.out.printf ("%d ", x[i]);
1009 // System.out.println();
1010 // Sorting.sort (x, new Sorting.Byte());
1011 // for (int i = 0; i < n; ++ i) System.out.printf ("%d ", x[i]);
1012 // System.out.println();
1013 // }
1014 //
1015 // /**
1016 // * Print a usage message and exit.
1017 // */
1018 // private static void usage()
1019 // {
1020 // System.err.println ("Usage: java edu.rit.util.Sorting <n> <seed>");
1021 // System.err.println ("<n> = Array length");
1022 // System.err.println ("<seed> = Random seed");
1023 // System.exit (1);
1024 // }
1025 }