ArraySorter.java revision 2224:2a8815d86b93
1220422Sgabor/* 2220422Sgabor * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved. 3210389Sgabor * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4210389Sgabor * 5210389Sgabor * This code is free software; you can redistribute it and/or modify it 6211496Sdes * under the terms of the GNU General Public License version 2 only, as 7210389Sgabor * published by the Free Software Foundation. Oracle designates this 8210389Sgabor * particular file as subject to the "Classpath" exception as provided 9210389Sgabor * by Oracle in the LICENSE file that accompanied this code. 10210389Sgabor * 11210389Sgabor * This code is distributed in the hope that it will be useful, but WITHOUT 12210389Sgabor * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13210389Sgabor * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14210389Sgabor * version 2 for more details (a copy is included in the LICENSE file that 15210389Sgabor * accompanied this code). 16210389Sgabor * 17210389Sgabor * You should have received a copy of the GNU General Public License version 18210389Sgabor * 2 along with this work; if not, write to the Free Software Foundation, 19210389Sgabor * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20210389Sgabor * 21210389Sgabor * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22210389Sgabor * or visit www.oracle.com if you need additional information or have any 23210389Sgabor * questions. 24210389Sgabor */ 25210389Sgabor 26210389Sgabor 27210389Sgabor/* 28210389Sgabor * The Original Code is HAT. The Initial Developer of the 29210389Sgabor * Original Code is Bill Foote, with contributions from others 30210389Sgabor * at JavaSoft/Sun. 31210389Sgabor */ 32210389Sgabor 33210389Sgaborpackage jdk.test.lib.hprof.util; 34210389Sgaborimport java.util.*; 35210389Sgabor 36210389Sgabor/** 37210389Sgabor * A singleton utility class that sorts an array of objects. 38210389Sgabor * <p> 39210389Sgabor * Use: 40210389Sgabor * <pre> 41226261Sgabor * 42210389Sgabor * Stuff[] arr = ...; 43210389Sgabor * ArraySorter.sort(arr, new Comparer() { 44210389Sgabor * public int compare(Object lhs, Object rhs) { 45210389Sgabor * return ((String) lhs).compareTo((String) rhs); 46210389Sgabor * } 47210389Sgabor * }); 48210389Sgabor * </pre> 49210389Sgabor * 50210389Sgabor * @author Bill Foote 51210389Sgabor */ 52226261Sgabor 53210389Sgaborpublic class ArraySorter { 54210389Sgabor 55210389Sgabor /** 56210389Sgabor * Sort the given array, using c for comparison 57210389Sgabor **/ 58210389Sgabor static public void sort(Object[] arr, Comparer c) { 59210389Sgabor quickSort(arr, c, 0, arr.length-1); 60210389Sgabor } 61210389Sgabor 62210389Sgabor 63210389Sgabor /** 64210389Sgabor * Sort an array of strings, using String.compareTo() 65210389Sgabor **/ 66210389Sgabor static public void sortArrayOfStrings(Object[] arr) { 67210389Sgabor sort(arr, new Comparer() { 68210622Sgabor public int compare(Object lhs, Object rhs) { 69210389Sgabor return ((String) lhs).compareTo((String) rhs); 70210389Sgabor } 71210389Sgabor }); 72210389Sgabor } 73210622Sgabor 74210622Sgabor 75210389Sgabor static private void swap(Object[] arr, int a, int b) { 76210389Sgabor Object tmp = arr[a]; 77210389Sgabor arr[a] = arr[b]; 78223009Sgabor arr[b] = tmp; 79210389Sgabor } 80210389Sgabor 81210389Sgabor // 82210389Sgabor // Sorts arr between from and to, inclusive. This is a quick, off-the-top- 83210389Sgabor // of-my-head quicksort: I haven't put any thought into optimizing it. 84210389Sgabor // I _did_ put thought into making sure it's safe (it will always 85210389Sgabor // terminate). Worst-case it's O(n^2), but it will usually run in 86226261Sgabor // in O(n log n). It's well-behaved if the list is already sorted, 87210389Sgabor // or nearly so. 88226261Sgabor // 89210389Sgabor static private void quickSort(Object[] arr, Comparer c, int from, int to) { 90210389Sgabor if (to <= from) 91210578Sgabor return; 92210578Sgabor int mid = (from + to) / 2; 93210578Sgabor if (mid != from) 94210389Sgabor swap(arr, mid, from); 95210389Sgabor Object pivot = arr[from]; // Simple-minded, but reasonable 96210389Sgabor int highestBelowPivot = from - 1; 97210389Sgabor int low = from+1; 98210389Sgabor int high = to; 99210389Sgabor // We now move low and high toward each other, maintaining the 100210389Sgabor // invariants: 101210389Sgabor // arr[i] <= pivot for all i < low 102210389Sgabor // arr[i] > pivot for all i > high 103210389Sgabor // As long as these invariants hold, and every iteration makes 104210389Sgabor // progress, we are safe. 105210389Sgabor while (low <= high) { 106210389Sgabor int cmp = c.compare(arr[low], pivot); 107210389Sgabor if (cmp <= 0) { // arr[low] <= pivot 108210389Sgabor if (cmp < 0) { 109226261Sgabor highestBelowPivot = low; 110210389Sgabor } 111210389Sgabor low++; 112210389Sgabor } else { 113210389Sgabor int c2; 114210389Sgabor for (;;) { 115210389Sgabor // arr[high] > pivot: 116210389Sgabor c2 = c.compare(arr[high], pivot); 117210389Sgabor if (c2 > 0) { 118210389Sgabor high--; 119210389Sgabor if (low > high) { 120210461Sgabor break; 121210389Sgabor } 122210389Sgabor } else { 123210389Sgabor break; 124210461Sgabor } 125210461Sgabor } 126210461Sgabor // At this point, low is never == high, BTW 127210389Sgabor if (low <= high) { 128211364Sgabor swap(arr, low, high); 129211364Sgabor if (c2 < 0) { 130210578Sgabor highestBelowPivot = low; 131210389Sgabor } 132210389Sgabor low++; 133210389Sgabor high--; 134210389Sgabor } 135210389Sgabor } 136210389Sgabor } 137210389Sgabor // At this point, low == high+1 138210389Sgabor // Now we just need to sort from from..highestBelowPivot 139210389Sgabor // and from high+1..to 140210389Sgabor if (highestBelowPivot > from) { 141210389Sgabor // pivot == pivot, so ensure algorithm terminates 142210389Sgabor swap(arr, from, highestBelowPivot); 143210389Sgabor quickSort(arr, c, from, highestBelowPivot-1); 144210389Sgabor } 145210461Sgabor quickSort(arr, c, high+1, to); 146210461Sgabor } 147210389Sgabor} 148210389Sgabor