xref: /external/replicaisland/src/com/replica/replicaisland/QuickSorter.java

/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.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.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.replica.replicaisland;

import java.util.Comparator;

public class QuickSorter<Type> extends Sorter<Type> {
    public void sort(Type[] array, int count, Comparator<Type> comparator) {
        quicksort(array, 0, count - 1, comparator);
    }

    // Quicksort implementation based on the one here:
    // http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
    /*************************************************************************
     *
     *  Generate N random real numbers between 0 and 1 and quicksort them.
     *
     *  On average, this quicksort algorithm runs in time proportional to
     *  N log N, independent of the input distribution. The algorithm
     *  uses Sedgewick's partitioning method which stops on equal keys.
     *  This protects against cases that make many textbook implementations,
     *  even randomized ones, go quadratic (e.g., all keys are the same).
     *
     *************************************************************************/

    /***********************************************************************
     *  Quicksort code from Sedgewick 7.1, 7.2.
     ***********************************************************************/

        // quicksort a[left] to a[right]
    public void quicksort(Type[] a, int left, int right, Comparator<Type> comparator) {
        if (right <= left) return;
        int i = partition(a, left, right, comparator);
        quicksort(a, left, i - 1, comparator);
        quicksort(a, i + 1, right, comparator);
    }

    // partition a[left] to a[right], assumes left < right
    private int partition(Type[] a, int left, int right, Comparator<Type> comparator) {
        int i = left - 1;
        int j = right;
        while (true) {
            while (comparator.compare(a[++i], a[right]) < 0) {     // find item on left to swap
            }                              // a[right] acts as sentinel
            while (comparator.compare(a[right], a[--j]) < 0) {    // find item on right to swap
                if (j == left) {
                    break;                 // don't go out-of-bounds
                }
            }
            if (i >= j) {
                break;                     // check if pointers cross
            }
            Type swap = a[i];                 // swap two elements into place
            a[i] = a[j];
            a[j] = swap;
        }
        Type swap = a[i]; // swap with partition element
        a[i] = a[right];
        a[right] = swap;
        return i;
    }
}