Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
BEGIN LICENSE BLOCK ***** Version: EPL 1.0/GPL 2.0/LGPL 2.1 The contents of this file are subject to the Eclipse Public License Version 1.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.eclipse.org/legal/epl-v10.html Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for the specific language governing rights and limitations under the License. Copyright (C) 2008-2009 Joseph LaFata <joe@quibb.org> Alternatively, the contents of this file may be used under the terms of either of the GNU General Public License Version 2 or later (the "GPL"), or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which case the provisions of the GPL or the LGPL are applicable instead of those above. If you wish to allow use of your version of this file only under the terms of either the GPL or the LGPL, and not to allow others to use your version of this file under the terms of the EPL, indicate your decision by deleting the provisions above and replace them with the notice and other provisions required by the GPL or the LGPL. If you do not delete the provisions above, a recipient may use your version of this file under the terms of any one of the EPL, the GPL or the LGPL. END LICENSE BLOCK ***
 
 package org.jruby.util;
 
 
 public class Qsort {
 private static final int SIZE_THRESHOLD = 16;
 
     public static void sort(Object[] aComparator c) {
         if(a.length < ) {
             insertionsort(a, 0, a.lengthc);
             return;
         }
 
         quicksort_loop(a, 0, a.lengthc);
     }
 
     public static void sort(Object[] aint beginint endComparator c) {
         if (begin < end) {
             if((end - begin) < ) {
                 insertionsort(abeginendc);
                 return;
             }
 
             quicksort_loop(abeginendc);
         }
     }
 
     private static void endTest(Object[] aint loint hiComparator c) {
         if (c.compare(a[lo], a[lo + 1]) <= 0) {
             if (c.compare(a[hi - 2], a[hi - 1]) > 0) {
                 bubbleUp(alohi-1, c);
             }
         } else {
             if (c.compare(a[hi - 2], a[hi - 1]) > 0) {
                 insertionsort(alohic);
             } else {
                 bubbleDown(alohi-1, c);
             }
         }
 
     }
 
     private static boolean seqtest(Object[] aint loint hiComparator c) {
         for (int i = lo + 1; i < hi - 2; ++i) {
             if (c.compare(a[i], a[i + 1]) > 0) {
                 return false;
             }
         }
         endTest(alohic);
         return true;
     }
 
     private static boolean revtest(Object[] aint loint hiComparator c) {
         for (int i = lo + 1; i < hi - 2; ++i) {
             if (c.compare(a[i], a[i + 1]) < 0) {
                 return false;
             }
         }
 
         // reverse the entire area of the array selected if it's reversed.
         int i = lo;
         int j = hi - 1;
         while (i < j) {
             swap(ai++, j--);
         }
         endTest(alohic);
         return true;
     }
 
 
 
    private static void quicksort_loop(Object[] aint loint hiComparator c) {
        final ArrayList<int[]> stack = new ArrayList<int[]>(16);
        int[] entry = new int[2];
        entry[0] = lo;
        entry[1] = hi;
        while (!stack.isEmpty() || entry != null) {
            if (entry == null) {
                entry = stack.remove(stack.size() - 1);
            }
            lo = entry[0];
            hi = entry[1];
            int midi = lo + (hi - lo) / 2;
            Object mid = a[midi];
            Object m1;
            Object m3;
            // do median of 7 if the array is over 200 elements.
            if ((hi - lo) >= 200) {
                int t = (hi - lo) / 8;
                m1 = med3(a[lo + t], a[lo + t * 2], a[lo + t * 3], c);
                m3 = med3(a[midi + t], a[midi + t * 2], a[midi + t * 3], c);
            } else {
                // if it's less than 200 do median of 3
                int t = (hi - lo) / 4;
                m1 = a[lo + t];
                m3 = a[midi + t];
            }
            mid = med3(m1midm3c);
            if (hi - lo >= 63) {
                if (c.compare(m1mid) <= 0 && c.compare(midm3) <= 0) {
                    if (seqtest(alohic)) {
                        entry = null;
                        continue;
                    }
                }
                else if (c.compare(m1mid) >= 0 && c.compare(midm3) >= 0) {
                    if (revtest(alohic)) {
                        entry = null;
                        continue;
                    }
                }
            }
            int[] p = partition(alohimidc);
            if(hi - p[1] >  && p[0] - lo > ) {
                entry[0] = p[1];
                entry[1] = hi;
                stack.add(entry);
                entry = new int[2];
                entry[0] = lo;
                entry[1] = p[0];
            } else if (hi - p[1] > ) {
                entry[0] = p[1];
                entry[1] = hi;
                insertionsort(alop[0], c);
            } else if (p[0] - lo > ) {
                entry[0] = lo;
                entry[1] = p[0];
                insertionsort(ap[1], hic);
            } else {
                insertionsort(alop[0], c);
                insertionsort(ap[1], hic);
                entry = null;
            }
        }
    }
    private static int[] partition(Object[] aint lo1int hiObject xComparator comp) {
        int lo = lo1;
        int i = loj = hic = 0;
        while (true) {
            while (i < j && (c = comp.compare(a[i], x)) <= 0) {
                if (c == 0) {
                    if (i > lo) {
                        swap(alo++, i);
                    } else {
                        lo++;
                    }
                }
                i++;
            }
            j--;
            while (j >= i && (c = comp.compare(xa[j])) < 0) {
                j--;
            }
            if (i > j) {
                break;
            }
            if (c == 0) {
                swap(aij);
                if (i > lo) {
                    swap(alo++, i);
                } else {
                    lo++;
                }
            } else {
                swap(aij);
            }
            i++;
        }
        c = ((i >= hi) ? hi-1 : i);
        while (c > lo1 && comp.compare(xa[c]) < 0 ) {
            c--;
        }
        lo--;
        while (lo >= lo1 && c > lo)
            swap(alo1++, c--);
        return new int[]{(c > lo) ? c + 1 : lo1i};
    }
    private static Object med3(Object loObject midObject hiComparator c) {
        if (c.compare(midlo) < 0) {
            if (c.compare(himid) < 0) {
                return mid;
            } else {
                if (c.compare(hilo) < 0) {
                    return hi;
                } else {
                    return lo;
                }
            }
        } else {
            if (c.compare(himid) < 0) {
                if (c.compare(hilo) < 0) {
                    return lo;
                } else {
                    return hi;
                }
            } else {
                return mid;
            }
        }
    }
    private static void insertionsort(Object[] aint loint hiComparator c) {
        for (int i = lo+1; i < hii++) {
            int j = i;
            Object t = a[j];
            while (j > lo && c.compare(ta[j - 1]) < 0) {
                a[j] = a[j - 1];
                --j;
            }
            a[j] = t;
        }
    }
    private static void bubbleDown(Object[] aint loint hiComparator c) {
        Object x = a[lo];
        while (lo < hi && c.compare(xa[lo+1]) > 0) {
            a[lo] = a[++lo];
        }
        a[lo] = x;
    }
    private static void bubbleUp(Object[] aint loint hiComparator c) {
        Object x = a[hi];
        while (hi > lo && c.compare(xa[hi-1]) < 0) {
            a[hi] = a[--hi];
        }
        a[hi] = x;
    }
    private static void swap(Object[] aint iint j) {
        Object t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
New to GrepCode? Check out our FAQ X