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> {
sort(Type[] array, int count, Comparator<Type> comparator)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]
quicksort(Type[] a, int left, int right, Comparator<Type> comparator)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
partition(Type[] a, int left, int right, Comparator<Type> comparator)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