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