Back to index

lightning-sunbird  0.9+nobinonly
QuickSort.java
Go to the documentation of this file.
00001 public class QuickSort {
00002        public static abstract class Comparator {
00003               public abstract int compare(Object obj1, Object obj2);
00004        }
00005 
00006        private Comparator mComparator;
00007 
00008        public QuickSort(Comparator comparator) {
00009               mComparator = comparator;
00010        }
00011 
00026        private void qsort(Object[] a, int lo0, int hi0) {
00027               int lo = lo0;
00028               int hi = hi0;
00029 
00030               if ( hi0 > lo0) {
00031                      /* Arbitrarily establishing partition element as the midpoint of
00032                      * the array.
00033                      */
00034                      Object mid = a[ ( lo0 + hi0 ) / 2 ];
00035 
00036                      // loop through the array until indices cross
00037                      while ( lo <= hi ) {
00038                             /* find the first element that is greater than or equal to 
00039                             * the partition element starting from the left Index.
00040                             */
00041                             while (( lo < hi0 ) && ( mComparator.compare(a[lo], mid) < 0 ))
00042                                    ++lo;
00043 
00044                             /* find an element that is smaller than or equal to 
00045                             * the partition element starting from the right Index.
00046                             */
00047                             while (( hi > lo0 ) && ( mComparator.compare(a[hi], mid) > 0 ))
00048                                    --hi;
00049 
00050                             // if the indexes have not crossed, swap
00051                             if ( lo <= hi ) {
00052                                    swap(a, lo, hi);
00053 
00054                                    ++lo;
00055                                    --hi;
00056                             }
00057                      }
00058 
00059                      /* If the right index has not reached the left side of array
00060                      * must now sort the left partition.
00061                      */
00062                      if ( lo0 < hi )
00063                             qsort( a, lo0, hi );
00064 
00065                      /* If the left index has not reached the right side of array
00066                      * must now sort the right partition.
00067                      */
00068                      if ( lo < hi0 )
00069                             qsort( a, lo, hi0 );
00070               }
00071        }
00072 
00073        private static void swap(Object[] a, int i, int j) {
00074               Object temp = a[i]; 
00075               a[i] = a[j];
00076               a[j] = temp;
00077        }
00078 
00079        public void sort(Object[] a) {
00080               qsort(a, 0, a.length - 1);
00081        }
00082        
00083        public void sort(Object[] a, int length) {
00084               qsort(a, 0, length - 1);
00085        }
00086 }