Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]
    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   }

Save This Page
Home » openjdk-7 » sun » misc » [javadoc | source]