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