1 /* 2 * Copyright (c) 2009-2010 jMonkeyEngine 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 package com.jme3.util; 33 34 import java.util.Arrays; 35 import java.util.Comparator; 36 37 /** 38 * Quick and merge sort implementations that create no garbage, unlike {@link 39 * Arrays#sort}. The merge sort is stable, the quick sort is not. 40 */ 41 public class SortUtil { 42 43 /** 44 * The size at or below which we will use insertion sort because it's 45 * probably faster. 46 */ 47 private static final int INSERTION_SORT_THRESHOLD = 7; 48 49 50 /** 51 procedure optimizedGnomeSort(a[]) 52 pos := 1 53 last := 0 54 while pos < length(a) 55 if (a[pos] >= a[pos-1]) 56 if (last != 0) 57 pos := last 58 last := 0 59 end if 60 pos := pos + 1 61 else 62 swap a[pos] and a[pos-1] 63 if (pos > 1) 64 if (last == 0) 65 last := pos 66 end if 67 pos := pos - 1 68 else 69 pos := pos + 1 70 end if 71 end if 72 end while 73 end procedure 74 */ 75 gsort(Object[] a, Comparator comp)76 public static void gsort(Object[] a, Comparator comp) { 77 int pos = 1; 78 int last = 0; 79 int length = a.length; 80 81 while (pos < length){ 82 if ( comp.compare(a[pos], a[pos-1]) >= 0 ){ 83 if (last != 0){ 84 pos = last; 85 last = 0; 86 } 87 pos ++; 88 }else{ 89 Object tmp = a[pos]; 90 a[pos] = a[pos-1]; 91 a[pos-1] = tmp; 92 93 if (pos > 1){ 94 if (last == 0){ 95 last = pos; 96 } 97 pos --; 98 }else{ 99 pos ++; 100 } 101 } 102 } 103 104 // int p = 0; 105 // int l = a.length; 106 // while (p < l) { 107 // int pm1 = p - 1; 108 // if (p == 0 || comp.compare(a[p], a[pm1]) >= 0) { 109 // p++; 110 // } else { 111 // Object t = a[p]; 112 // a[p] = a[pm1]; 113 // a[pm1] = t; 114 // p--; 115 // } 116 // } 117 } 118 test(Float[] original, Float[] sorted, Comparator<Float> ic)119 private static void test(Float[] original, Float[] sorted, Comparator<Float> ic) { 120 long time, dt; 121 122 time = System.nanoTime(); 123 for (int i = 0; i < 1000000; i++) { 124 System.arraycopy(original, 0, sorted, 0, original.length); 125 gsort(sorted, ic); 126 } 127 dt = System.nanoTime() - time; 128 System.out.println("GSort " + (dt/1000000.0) + " ms"); 129 130 time = System.nanoTime(); 131 for (int i = 0; i < 1000000; i++) { 132 System.arraycopy(original, 0, sorted, 0, original.length); 133 qsort(sorted, ic); 134 } 135 dt = System.nanoTime() - time; 136 System.out.println("QSort " + (dt/1000000.0) + " ms"); 137 138 time = System.nanoTime(); 139 for (int i = 0; i < 1000000; i++) { 140 System.arraycopy(original, 0, sorted, 0, original.length); 141 msort(original, sorted, ic); 142 } 143 dt = System.nanoTime() - time; 144 System.out.println("MSort " + (dt/1000000.0) + " ms"); 145 146 time = System.nanoTime(); 147 for (int i = 0; i < 1000000; i++) { 148 System.arraycopy(original, 0, sorted, 0, original.length); 149 Arrays.sort(sorted, ic); 150 } 151 dt = System.nanoTime() - time; 152 System.out.println("ASort " + (dt/1000000.0) + " ms"); 153 } 154 main(String[] args)155 public static void main(String[] args) { 156 Comparator<Float> ic = new Comparator<Float>() { 157 158 public int compare(Float o1, Float o2) { 159 return (int) (o1 - o2); 160 } 161 }; 162 Float[] original = new Float[]{2f, 1f, 5f, 3f, 4f, 6f, 8f, 9f, 163 11f, 10f, 12f, 13f, 14f, 15f, 7f, 19f, 20f, 18f, 16f, 17f, 164 21f, 23f, 22f, 24f, 25f, 27f, 26f, 29f, 28f, 30f, 31f}; 165 Float[] sorted = new Float[original.length]; 166 167 while (true) { 168 test(original, sorted, ic); 169 } 170 } 171 172 /** 173 * Quick sorts the supplied array using the specified comparator. 174 */ qsort(Object[] a, Comparator comp)175 public static void qsort(Object[] a, Comparator comp) { 176 qsort(a, 0, a.length - 1, comp); 177 } 178 179 /** 180 * Quick sorts the supplied array using the specified comparator. 181 * 182 * @param lo0 the index of the lowest element to include in the sort. 183 * @param hi0 the index of the highest element to include in the sort. 184 */ 185 @SuppressWarnings("unchecked") qsort(Object[] a, int lo0, int hi0, Comparator comp)186 public static void qsort(Object[] a, int lo0, int hi0, Comparator comp) { 187 // bail out if we're already done 188 if (hi0 <= lo0) { 189 return; 190 } 191 192 // if this is a two element list, do a simple sort on it 193 Object t; 194 if (hi0 - lo0 == 1) { 195 // if they're not already sorted, swap them 196 if (comp.compare(a[hi0], a[lo0]) < 0) { 197 t = a[lo0]; 198 a[lo0] = a[hi0]; 199 a[hi0] = t; 200 } 201 return; 202 } 203 204 // the middle element in the array is our partitioning element 205 Object mid = a[(lo0 + hi0) / 2]; 206 207 // set up our partitioning boundaries 208 int lo = lo0 - 1, hi = hi0 + 1; 209 210 // loop through the array until indices cross 211 for (;;) { 212 // find the first element that is greater than or equal to 213 // the partition element starting from the left Index. 214 while (comp.compare(a[++lo], mid) < 0); 215 216 // find an element that is smaller than or equal to 217 // the partition element starting from the right Index. 218 while (comp.compare(mid, a[--hi]) < 0); 219 220 // swap the two elements or bail out of the loop 221 if (hi > lo) { 222 t = a[lo]; 223 a[lo] = a[hi]; 224 a[hi] = t; 225 } else { 226 break; 227 } 228 } 229 230 // if the right index has not reached the left side of array 231 // must now sort the left partition 232 if (lo0 < lo - 1) { 233 qsort(a, lo0, lo - 1, comp); 234 } 235 236 // if the left index has not reached the right side of array 237 // must now sort the right partition 238 if (hi + 1 < hi0) { 239 qsort(a, hi + 1, hi0, comp); 240 } 241 } 242 qsort(int[] a, int lo0, int hi0, Comparator comp)243 public static void qsort(int[] a, int lo0, int hi0, Comparator comp) { 244 // bail out if we're already done 245 if (hi0 <= lo0) { 246 return; 247 } 248 249 // if this is a two element list, do a simple sort on it 250 int t; 251 if (hi0 - lo0 == 1) { 252 // if they're not already sorted, swap them 253 if (comp.compare(a[hi0], a[lo0]) < 0) { 254 t = a[lo0]; 255 a[lo0] = a[hi0]; 256 a[hi0] = t; 257 } 258 return; 259 } 260 261 // the middle element in the array is our partitioning element 262 int mid = a[(lo0 + hi0) / 2]; 263 264 // set up our partitioning boundaries 265 int lo = lo0 - 1, hi = hi0 + 1; 266 267 // loop through the array until indices cross 268 for (;;) { 269 // find the first element that is greater than or equal to 270 // the partition element starting from the left Index. 271 while (comp.compare(a[++lo], mid) < 0); 272 273 // find an element that is smaller than or equal to 274 // the partition element starting from the right Index. 275 while (comp.compare(mid, a[--hi]) < 0); 276 277 // swap the two elements or bail out of the loop 278 if (hi > lo) { 279 t = a[lo]; 280 a[lo] = a[hi]; 281 a[hi] = t; 282 } else { 283 break; 284 } 285 } 286 287 // if the right index has not reached the left side of array 288 // must now sort the left partition 289 if (lo0 < lo - 1) { 290 qsort(a, lo0, lo - 1, comp); 291 } 292 293 // if the left index has not reached the right side of array 294 // must now sort the right partition 295 if (hi + 1 < hi0) { 296 qsort(a, hi + 1, hi0, comp); 297 } 298 } 299 300 /** 301 * Merge sort 302 */ msort(Object[] src, Object[] dest, Comparator comp)303 public static void msort(Object[] src, Object[] dest, Comparator comp){ 304 msort(src, dest, 0, src.length - 1, comp); 305 } 306 307 /** 308 * Merge sort 309 * 310 * @param src Source array 311 * @param dest Destination array 312 * @param low Index of beginning element 313 * @param high Index of end element 314 * @param comp Comparator 315 */ msort(Object[] src, Object[] dest, int low, int high, Comparator comp)316 public static void msort(Object[] src, Object[] dest, int low, int high, 317 Comparator comp) { 318 if(low < high) { 319 int center = (low + high) / 2; 320 msort(src, dest, low, center, comp); 321 msort(src, dest, center + 1, high, comp); 322 merge(src, dest, low, center + 1, high, comp); 323 } 324 } 325 merge(Object[] src, Object[] dest, int low, int middle, int high, Comparator comp)326 private static void merge(Object[] src, Object[] dest, 327 int low, int middle, int high, Comparator comp) { 328 int leftEnd = middle - 1; 329 int pos = low; 330 int numElements = high - low + 1; 331 332 while (low <= leftEnd && middle <= high) { 333 if (comp.compare(src[low], src[middle]) <= 0) { 334 dest[pos++] = src[low++]; 335 } else { 336 dest[pos++] = src[middle++]; 337 } 338 } 339 340 while (low <= leftEnd) { 341 dest[pos++] = src[low++]; 342 } 343 344 while (middle <= high) { 345 dest[pos++] = src[middle++]; 346 } 347 348 for (int i = 0; i < numElements; i++, high--) { 349 src[high] = dest[high]; 350 } 351 } 352 } 353