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 }