1 /*
   2  * Copyright (c) 1996, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 /**
  27  * Sort: a class that uses the quicksort algorithm to sort an
  28  *       array of objects.
  29  *
  30  * @author Sunita Mani
  31  */
  32 
  33 package sun.misc;
  34 
  35 public class Sort {
  36 
  37     private static void swap(Object arr[], int i, int j) {
  38         Object tmp;
  39 
  40         tmp = arr[i];
  41         arr[i] = arr[j];
  42         arr[j] = tmp;
  43     }
  44 
  45     /**
  46      * quicksort the array of objects.
  47      *
  48      * @param arr[] - an array of objects
  49      * @param left - the start index - from where to begin sorting
  50      * @param right - the last index.
  51      * @param comp - an object that implemnts the Compare interface to resolve thecomparison.
  52      */
  53     public static void quicksort(Object arr[], int left, int right, Compare comp) {
  54         int i, last;
  55 
  56         if (left >= right) { /* do nothing if array contains fewer than two */
  57             return;          /* two elements */
  58         }
  59         swap(arr, left, (left+right) / 2);
  60         last = left;
  61         for (i = left+1; i <= right; i++) {
  62             if (comp.doCompare(arr[i], arr[left]) < 0) {
  63                 swap(arr, ++last, i);
  64             }
  65         }
  66         swap(arr, left, last);
  67         quicksort(arr, left, last-1, comp);
  68         quicksort(arr, last+1, right, comp);
  69     }
  70 
  71     public static void quicksort(Object arr[], Compare comp) {
  72         quicksort(arr, 0, arr.length-1, comp);
  73     }
  74 }