gdx/src/com/badlogic/gdx/utils/QuickSelect.java

   1 /*******************************************************************************
   2  * Copyright 2011 See AUTHORS file.
   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.badlogic.gdx.utils;
  18
  19 import java.util.Comparator;
  20
  21
  22 /**
  23  * Implementation of Tony Hoare's quickselect algorithm.
  24  * Running time is generally O(n), but worst case is O(n**2)
  25  * Pivot choice is median of three method, providing better performance
  26  * than a random pivot for partially sorted data.
  27  * @author Jon Renner
  28  */
  29 public class QuickSelect<T> {
  30         private T[] array;
  31         private Comparator<? super T> comp;
  32
  33         public int select(T[] items, Comparator<T> comp, int n, int size) {
  34                 this.array = items;
  35                 this.comp = comp;
  36                 return recursiveSelect(0, size - 1, n);
  37         }
  38
  39         private int partition(int left, int right, int pivot) {
  40                 T pivotValue = array[pivot];
  41                 swap(right, pivot);
  42                 int storage = left;
  43                 for (int i = left; i < right; i++) {
  44                         if (comp.compare(array[i], pivotValue) < 0) {
  45                                 swap(storage, i);
  46                                 storage++;
  47                         }
  48                 }
  49                 swap(right, storage);
  50                 return storage;
  51         }
  52
  53         private int recursiveSelect(int left, int right, int k) {
  54                 if (left == right) return left;
  55                 int pivotIndex = medianOfThreePivot(left, right);
  56                 int pivotNewIndex = partition(left, right, pivotIndex);
  57                 int pivotDist = (pivotNewIndex - left) + 1;
  58                 int result;
  59                 if (pivotDist == k) {
  60                         result = pivotNewIndex;
  61                 }
  62                 else if (k < pivotDist) {
  63                         result = recursiveSelect(left, pivotNewIndex - 1, k);
  64                 } else {
  65                         result = recursiveSelect(pivotNewIndex + 1, right, k - pivotDist);
  66                 }
  67                 return result;
  68         }
  69
  70         /** Median of Three has the potential to outperform a random pivot, especially for partially sorted arrays */
  71         private int medianOfThreePivot(int leftIdx, int rightIdx) {
  72                 T left = array[leftIdx];
  73                 int midIdx = (leftIdx + rightIdx) / 2;
  74                 T mid = array[midIdx];
  75                 T right = array[rightIdx];
  76
  77                 // spaghetti median of three algorithm
  78                 // does at most 2 comparisons
  79                 if (comp.compare(left, mid) > 0) {
  80                         if (comp.compare(mid, right) > 0) {
  81                                 return midIdx;
  82                         } else if (comp.compare(left, right) > 0) {
  83                                 return rightIdx;
  84                         } else {
  85                                 return leftIdx;
  86                         }
  87                 } else {
  88                         if (comp.compare(left, right) > 0) {
  89                                 return leftIdx;
  90                         } else if (comp.compare(mid, right) > 0) {
  91                                 return rightIdx;
  92                         } else {
  93                                 return midIdx;
  94                         }
  95                 }
  96         }
  97
  98         private void swap(int left, int right) {
  99                 T tmp = array[left];
 100                 array[left] = array[right];
 101                 array[right] = tmp;
 102         }
 103 }