1 /* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.replica.replicaisland; 18 19 import java.util.Comparator; 20 21 public class QuickSorter<Type> extends Sorter<Type> { 22 public void sort(Type[] array, int count, Comparator<Type> comparator) { 23 quicksort(array, 0, count - 1, comparator); 24 } 25 26 // Quicksort implementation based on the one here: 27 // http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html 28 /************************************************************************* 29 * 30 * Generate N random real numbers between 0 and 1 and quicksort them. 31 * 32 * On average, this quicksort algorithm runs in time proportional to 33 * N log N, independent of the input distribution. The algorithm 34 * uses Sedgewick's partitioning method which stops on equal keys. 35 * This protects against cases that make many textbook implementations, 36 * even randomized ones, go quadratic (e.g., all keys are the same). 37 * 38 *************************************************************************/ 39 40 /*********************************************************************** 41 * Quicksort code from Sedgewick 7.1, 7.2. 42 ***********************************************************************/ 43 44 // quicksort a[left] to a[right] 45 public void quicksort(Type[] a, int left, int right, Comparator<Type> comparator) { 46 if (right <= left) return; 47 int i = partition(a, left, right, comparator); 48 quicksort(a, left, i - 1, comparator); 49 quicksort(a, i + 1, right, comparator); 50 } 51 52 // partition a[left] to a[right], assumes left < right 53 private int partition(Type[] a, int left, int right, Comparator<Type> comparator) { 54 int i = left - 1; 55 int j = right; 56 while (true) { 57 while (comparator.compare(a[++i], a[right]) < 0) { // find item on left to swap 58 } // a[right] acts as sentinel 59 while (comparator.compare(a[right], a[--j]) < 0) { // find item on right to swap 60 if (j == left) { 61 break; // don't go out-of-bounds 62 } 63 } 64 if (i >= j) { 65 break; // check if pointers cross 66 } 67 Type swap = a[i]; // swap two elements into place 68 a[i] = a[j]; 69 a[j] = swap; 70 } 71 Type swap = a[i]; // swap with partition element 72 a[i] = a[right]; 73 a[right] = swap; 74 return i; 75 } 76 } 77
