View Javadoc
1 package org.apache.turbine.util; 2 3 /* ==================================================================== 4 * The Apache Software License, Version 1.1 5 * 6 * Copyright (c) 2001 The Apache Software Foundation. All rights 7 * reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in 18 * the documentation and/or other materials provided with the 19 * distribution. 20 * 21 * 3. The end-user documentation included with the redistribution, 22 * if any, must include the following acknowledgment: 23 * "This product includes software developed by the 24 * Apache Software Foundation (http://www.apache.org/)." 25 * Alternately, this acknowledgment may appear in the software itself, 26 * if and wherever such third-party acknowledgments normally appear. 27 * 28 * 4. The names "Apache" and "Apache Software Foundation" and 29 * "Apache Turbine" must not be used to endorse or promote products 30 * derived from this software without prior written permission. For 31 * written permission, please contact apache@apache.org. 32 * 33 * 5. Products derived from this software may not be called "Apache", 34 * "Apache Turbine", nor may "Apache" appear in their name, without 35 * prior written permission of the Apache Software Foundation. 36 * 37 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 38 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 39 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 40 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 41 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 42 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 43 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 44 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 45 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 46 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 47 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 48 * SUCH DAMAGE. 49 * ==================================================================== 50 * 51 * This software consists of voluntary contributions made by many 52 * individuals on behalf of the Apache Software Foundation. For more 53 * information on the Apache Software Foundation, please see 54 * <http://www.apache.org/>;. 55 */ 56 57 /*** 58 * QuickSort - adapted from Doug Lea's Public Domain collection 59 * library. 60 * 61 * @author <a href="mailto:mbryson@mindspring.com">Dave Bryson</a> 62 * @version $Id: QuickSort.java,v 1.1.1.1 2001/08/16 05:09:40 jvanzyl Exp $ 63 */ 64 public class QuickSort 65 { 66 /*** 67 * Sort array of Objects using the QuickSort algorithm. 68 * 69 * @param s An Object[]. 70 * @param lo The current lower bound. 71 * @param hi The current upper bound. 72 * @param cmp A Comparable to compare two elements. 73 */ 74 public static void quickSort(Object s[], 75 int lo, 76 int hi, 77 Comparable cmp) 78 { 79 if (lo >= hi) 80 return; 81 82 /* 83 * Use median-of-three(lo, mid, hi) to pick a partition. Also 84 * swap them into relative order while we are at it. 85 */ 86 int mid = (lo + hi) / 2; 87 88 if (cmp.compare(s[lo], s[mid]) > 0) 89 { 90 // Swap. 91 Object tmp = s[lo]; 92 s[lo] = s[mid]; 93 s[mid] = tmp; 94 } 95 96 if (cmp.compare(s[mid], s[hi]) > 0) 97 { 98 // Swap . 99 Object tmp = s[mid]; 100 s[mid] = s[hi]; 101 s[hi] = tmp; 102 103 if (cmp.compare(s[lo], s[mid]) > 0) 104 { 105 // Swap. 106 Object tmp2 = s[lo]; 107 s[lo] = s[mid]; 108 s[mid] = tmp2; 109 } 110 } 111 112 // Start one past lo since already handled lo. 113 int left = lo+1; 114 115 // Similarly, end one before hi since already handled hi. 116 int right = hi-1; 117 118 // If there are three or fewer elements, we are done. 119 if (left >= right) 120 return; 121 122 Object partition = s[mid]; 123 124 for (;;) 125 { 126 while (cmp.compare(s[right], partition) > 0) 127 --right; 128 129 while (left < right && 130 cmp.compare(s[left], partition) <= 0) 131 ++left; 132 133 if (left < right) 134 { 135 // Swap. 136 Object tmp = s[left]; 137 s[left] = s[right]; 138 s[right] = tmp; 139 140 --right; 141 } 142 else 143 break; 144 } 145 quickSort(s, lo, left, cmp); 146 quickSort(s, left+1, hi, cmp); 147 } 148 149 /*** 150 * Sorts and array of objects. 151 * 152 * @param data An Object[]. 153 * @param cmp A Comparable to compare two elements. 154 */ 155 public void sort(Object[] data, 156 Comparable cmp) 157 { 158 QuickSort.quickSort(data, 159 0, 160 data.length - 1, 161 cmp); 162 } 163 }

This page was automatically generated by Maven