View Javadoc
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] &lt; 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] &lt; 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] &lt; 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] &lt; 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] &lt; 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] &lt; 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] &lt; 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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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>&nbsp;log&nbsp;<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 }