1 //****************************************************************************** 2 // 3 // File: Sorting.java 4 // Package: edu.rit.util 5 // Unit: Class edu.rit.util.Sorting 6 // 7 // This Java source file is copyright (C) 2011 by Alan Kaminsky. All rights 8 // reserved. For further information, contact the author, Alan Kaminsky, at 9 // ark@cs.rit.edu. 10 // 11 // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free 12 // software; you can redistribute it and/or modify it under the terms of the GNU 13 // General Public License as published by the Free Software Foundation; either 14 // version 3 of the License, or (at your option) any later version. 15 // 16 // PJ is distributed in the hope that it will be useful, but WITHOUT ANY 17 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 18 // A PARTICULAR PURPOSE. See the GNU General Public License for more details. 19 // 20 // Linking this library statically or dynamically with other modules is making a 21 // combined work based on this library. Thus, the terms and conditions of the GNU 22 // General Public License cover the whole combination. 23 // 24 // As a special exception, the copyright holders of this library give you 25 // permission to link this library with independent modules to produce an 26 // executable, regardless of the license terms of these independent modules, and 27 // to copy and distribute the resulting executable under terms of your choice, 28 // provided that you also meet, for each linked independent module, the terms 29 // and conditions of the license of that module. An independent module is a module 30 // which is not derived from or based on this library. If you modify this library, 31 // you may extend this exception to your version of the library, but you are not 32 // obligated to do so. If you do not wish to do so, delete this exception 33 // statement from your version. 34 // 35 // A copy of the GNU General Public License is provided in the file gpl.txt. You 36 // may also obtain a copy of the GNU General Public License on the World Wide 37 // Web at http://www.gnu.org/licenses/gpl.html. 38 // 39 //****************************************************************************** 40 package edu.rit.util; 41 42 /** 43 * Class Sorting provides static methods for sorting arrays of primitive types 44 * and object types. 45 * <P> 46 * <I>Note:</I> The operations in class Sorting are not multiple thread safe. 47 * 48 * @author Alan Kaminsky 49 * @version 02-Nov-2011 50 */ 51 public class Sorting { 52 53 // Prevent construction. 54 private Sorting() { 55 } 56 57 // Exported helper classes. 58 /** 59 * Class Sorting.Byte is the base class for a helper object used to sort an 60 * array of type <code>byte[]</code>. 61 * 62 * @author Alan Kaminsky 63 * @version 20-Oct-2010 64 */ 65 public static class Byte { 66 67 /** 68 * Compare two elements in the given array. This determines the order of 69 * the elements in the sorted array. 70 * <P> 71 * The default implementation returns true if <code>x[a] < x[b]</code>, 72 * which sorts the array into ascending order. A subclass can override 73 * this method to obtain a different ordering criterion; for example, 74 * descending order. 75 * 76 * @param x Array being sorted. 77 * @param a Index of first array element being compared. 78 * @param b Index of second array element being compared. 79 * 80 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 81 * desired ordering, false otherwise. 82 */ 83 public boolean comesBefore(byte[] x, 84 int a, 85 int b) { 86 return x[a] < x[b]; 87 } 88 89 /** 90 * Swap two elements in the given array. 91 * <P> 92 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 93 * subclass can override this method to do something different; for 94 * example, to swap the elements of other arrays in addition to 95 * <code>x</code>. 96 * 97 * @param x Array being sorted. 98 * @param a Index of first array element being swapped. 99 * @param b Index of second array element being swapped. 100 */ 101 public void swap(byte[] x, 102 int a, 103 int b) { 104 byte t = x[a]; 105 x[a] = x[b]; 106 x[b] = t; 107 } 108 } 109 110 /** 111 * Class Sorting.Character is the base class for a helper object used to 112 * sort an array of type <code>char[]</code>. 113 * 114 * @author Alan Kaminsky 115 * @version 20-Oct-2010 116 */ 117 public static class Character { 118 119 /** 120 * Compare two elements in the given array. This determines the order of 121 * the elements in the sorted array. 122 * <P> 123 * The default implementation returns true if <code>x[a] < x[b]</code>, 124 * which sorts the array into ascending order. A subclass can override 125 * this method to obtain a different ordering criterion; for example, 126 * descending order. 127 * 128 * @param x Array being sorted. 129 * @param a Index of first array element being compared. 130 * @param b Index of second array element being compared. 131 * 132 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 133 * desired ordering, false otherwise. 134 */ 135 public boolean comesBefore(char[] x, 136 int a, 137 int b) { 138 return x[a] < x[b]; 139 } 140 141 /** 142 * Swap two elements in the given array. 143 * <P> 144 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 145 * subclass can override this method to do something different; for 146 * example, to swap the elements of other arrays in addition to 147 * <code>x</code>. 148 * 149 * @param x Array being sorted. 150 * @param a Index of first array element being swapped. 151 * @param b Index of second array element being swapped. 152 */ 153 public void swap(char[] x, 154 int a, 155 int b) { 156 char t = x[a]; 157 x[a] = x[b]; 158 x[b] = t; 159 } 160 } 161 162 /** 163 * Class Sorting.Short is the base class for a helper object used to sort an 164 * array of type <code>short[]</code>. 165 * 166 * @author Alan Kaminsky 167 * @version 20-Oct-2010 168 */ 169 public static class Short { 170 171 /** 172 * Compare two elements in the given array. This determines the order of 173 * the elements in the sorted array. 174 * <P> 175 * The default implementation returns true if <code>x[a] < x[b]</code>, 176 * which sorts the array into ascending order. A subclass can override 177 * this method to obtain a different ordering criterion; for example, 178 * descending order. 179 * 180 * @param x Array being sorted. 181 * @param a Index of first array element being compared. 182 * @param b Index of second array element being compared. 183 * 184 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 185 * desired ordering, false otherwise. 186 */ 187 public boolean comesBefore(short[] x, 188 int a, 189 int b) { 190 return x[a] < x[b]; 191 } 192 193 /** 194 * Swap two elements in the given array. 195 * <P> 196 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 197 * subclass can override this method to do something different; for 198 * example, to swap the elements of other arrays in addition to 199 * <code>x</code>. 200 * 201 * @param x Array being sorted. 202 * @param a Index of first array element being swapped. 203 * @param b Index of second array element being swapped. 204 */ 205 public void swap(short[] x, 206 int a, 207 int b) { 208 short t = x[a]; 209 x[a] = x[b]; 210 x[b] = t; 211 } 212 } 213 214 /** 215 * Class Sorting.Integer is the base class for a helper object used to sort 216 * an array of type <code>int[]</code>. 217 * 218 * @author Alan Kaminsky 219 * @version 20-Oct-2010 220 */ 221 public static class Integer { 222 223 /** 224 * Compare two elements in the given array. This determines the order of 225 * the elements in the sorted array. 226 * <P> 227 * The default implementation returns true if <code>x[a] < x[b]</code>, 228 * which sorts the array into ascending order. A subclass can override 229 * this method to obtain a different ordering criterion; for example, 230 * descending order. 231 * 232 * @param x Array being sorted. 233 * @param a Index of first array element being compared. 234 * @param b Index of second array element being compared. 235 * 236 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 237 * desired ordering, false otherwise. 238 */ 239 public boolean comesBefore(int[] x, 240 int a, 241 int b) { 242 return x[a] < x[b]; 243 } 244 245 /** 246 * Swap two elements in the given array. 247 * <P> 248 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 249 * subclass can override this method to do something different; for 250 * example, to swap the elements of other arrays in addition to 251 * <code>x</code>. 252 * 253 * @param x Array being sorted. 254 * @param a Index of first array element being swapped. 255 * @param b Index of second array element being swapped. 256 */ 257 public void swap(int[] x, 258 int a, 259 int b) { 260 int t = x[a]; 261 x[a] = x[b]; 262 x[b] = t; 263 } 264 } 265 266 /** 267 * Class Sorting.Long is the base class for a helper object used to sort an 268 * array of type <code>long[]</code>. 269 * 270 * @author Alan Kaminsky 271 * @version 20-Oct-2010 272 */ 273 public static class Long { 274 275 /** 276 * Compare two elements in the given array. This determines the order of 277 * the elements in the sorted array. 278 * <P> 279 * The default implementation returns true if <code>x[a] < x[b]</code>, 280 * which sorts the array into ascending order. A subclass can override 281 * this method to obtain a different ordering criterion; for example, 282 * descending order. 283 * 284 * @param x Array being sorted. 285 * @param a Index of first array element being compared. 286 * @param b Index of second array element being compared. 287 * 288 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 289 * desired ordering, false otherwise. 290 */ 291 public boolean comesBefore(long[] x, 292 int a, 293 int b) { 294 return x[a] < x[b]; 295 } 296 297 /** 298 * Swap two elements in the given array. 299 * <P> 300 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 301 * subclass can override this method to do something different; for 302 * example, to swap the elements of other arrays in addition to 303 * <code>x</code>. 304 * 305 * @param x Array being sorted. 306 * @param a Index of first array element being swapped. 307 * @param b Index of second array element being swapped. 308 */ 309 public void swap(long[] x, 310 int a, 311 int b) { 312 long t = x[a]; 313 x[a] = x[b]; 314 x[b] = t; 315 } 316 } 317 318 /** 319 * Class Sorting.Float is the base class for a helper object used to sort an 320 * array of type <code>float[]</code>. 321 * 322 * @author Alan Kaminsky 323 * @version 20-Oct-2010 324 */ 325 public static class Float { 326 327 /** 328 * Compare two elements in the given array. This determines the order of 329 * the elements in the sorted array. 330 * <P> 331 * The default implementation returns true if <code>x[a] < x[b]</code>, 332 * which sorts the array into ascending order. A subclass can override 333 * this method to obtain a different ordering criterion; for example, 334 * descending order. 335 * 336 * @param x Array being sorted. 337 * @param a Index of first array element being compared. 338 * @param b Index of second array element being compared. 339 * 340 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 341 * desired ordering, false otherwise. 342 */ 343 public boolean comesBefore(float[] x, 344 int a, 345 int b) { 346 return x[a] < x[b]; 347 } 348 349 /** 350 * Swap two elements in the given array. 351 * <P> 352 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 353 * subclass can override this method to do something different; for 354 * example, to swap the elements of other arrays in addition to 355 * <code>x</code>. 356 * 357 * @param x Array being sorted. 358 * @param a Index of first array element being swapped. 359 * @param b Index of second array element being swapped. 360 */ 361 public void swap(float[] x, 362 int a, 363 int b) { 364 float t = x[a]; 365 x[a] = x[b]; 366 x[b] = t; 367 } 368 } 369 370 /** 371 * Class Sorting.Double is the base class for a helper object used to sort 372 * an array of type <code>double[]</code>. 373 * 374 * @author Alan Kaminsky 375 * @version 20-Oct-2010 376 */ 377 public static class Double { 378 379 /** 380 * Compare two elements in the given array. This determines the order of 381 * the elements in the sorted array. 382 * <P> 383 * The default implementation returns true if <code>x[a] < x[b]</code>, 384 * which sorts the array into ascending order. A subclass can override 385 * this method to obtain a different ordering criterion; for example, 386 * descending order. 387 * 388 * @param x Array being sorted. 389 * @param a Index of first array element being compared. 390 * @param b Index of second array element being compared. 391 * 392 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 393 * desired ordering, false otherwise. 394 */ 395 public boolean comesBefore(double[] x, 396 int a, 397 int b) { 398 return x[a] < x[b]; 399 } 400 401 /** 402 * Swap two elements in the given array. 403 * <P> 404 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 405 * subclass can override this method to do something different; for 406 * example, to swap the elements of other arrays in addition to 407 * <code>x</code>. 408 * 409 * @param x Array being sorted. 410 * @param a Index of first array element being swapped. 411 * @param b Index of second array element being swapped. 412 */ 413 public void swap(double[] x, 414 int a, 415 int b) { 416 double t = x[a]; 417 x[a] = x[b]; 418 x[b] = t; 419 } 420 } 421 422 /** 423 * Class Sorting.Object is the abstract base class for a helper object used 424 * to sort an array of objects of type <code>T[]</code>. 425 * 426 * @param <T> Data type of the array elements. 427 * 428 * @author Alan Kaminsky 429 * @version 20-Oct-2010 430 */ 431 public static abstract class Object<T> { 432 433 /** 434 * Compare two elements in the given array. This determines the order of 435 * the elements in the sorted array. 436 * 437 * @param x Array being sorted. 438 * @param a Index of first array element being compared. 439 * @param b Index of second array element being compared. 440 * 441 * @return True if <code>x[a]</code> comes before <code>x[b]</code> in the 442 * desired ordering, false otherwise. 443 */ 444 public abstract boolean comesBefore(T[] x, 445 int a, 446 int b); 447 448 /** 449 * Swap two elements in the given array. 450 * <P> 451 * The default implementation swaps <code>x[a]</code> with <code>x[b]</code>. A 452 * subclass can override this method to do something different; for 453 * example, to swap the elements of other arrays in addition to 454 * <code>x</code>. 455 * 456 * @param x Array being sorted. 457 * @param a Index of first array element being swapped. 458 * @param b Index of second array element being swapped. 459 */ 460 public void swap(T[] x, 461 int a, 462 int b) { 463 T t = x[a]; 464 x[a] = x[b]; 465 x[b] = t; 466 } 467 } 468 469 // Exported operations. 470 /** 471 * Sort the given array of type <code>byte[]</code>. The given helper object is 472 * used to determine the desired ordering of the array elements and to swap 473 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 474 * algorithm is used. 475 * 476 * @param x Array to be sorted. 477 * @param helper Helper object. 478 * @return The array that was sorted (<code>x</code>). 479 */ 480 public static byte[] sort(byte[] x, 481 Sorting.Byte helper) { 482 int n = x.length; 483 for (int i = 2; i <= n; ++i) { 484 siftUp(x, i, helper); 485 } 486 for (int i = n; i >= 2; --i) { 487 helper.swap(x, 0, i - 1); 488 siftDown(x, i - 1, helper); 489 } 490 return x; 491 } 492 493 private static void siftUp(byte[] x, 494 int c, // 1-based index 495 Sorting.Byte helper) { 496 int p = c >> 1; // 1-based index 497 while (p >= 1) { 498 if (helper.comesBefore(x, p - 1, c - 1)) { 499 helper.swap(x, p - 1, c - 1); 500 } else { 501 break; 502 } 503 c = p; 504 p = c >> 1; 505 } 506 } 507 508 private static void siftDown(byte[] x, 509 int n, // 1-based index 510 Sorting.Byte helper) { 511 int p = 1; // 1-based index 512 int ca = 2; // 1-based index 513 int cb = 3; // 1-based index 514 while (ca <= n) { 515 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 516 if (helper.comesBefore(x, p - 1, cb - 1)) { 517 helper.swap(x, p - 1, cb - 1); 518 p = cb; 519 } else { 520 break; 521 } 522 } else { 523 if (helper.comesBefore(x, p - 1, ca - 1)) { 524 helper.swap(x, p - 1, ca - 1); 525 p = ca; 526 } else { 527 break; 528 } 529 } 530 ca = p << 1; 531 cb = ca + 1; 532 } 533 } 534 535 /** 536 * Sort the given array of type <code>char[]</code>. The given helper object is 537 * used to determine the desired ordering of the array elements and to swap 538 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 539 * algorithm is used. 540 * 541 * @param x Array to be sorted. 542 * @param helper Helper object. 543 * @return The array that was sorted (<code>x</code>). 544 */ 545 public static char[] sort(char[] x, 546 Sorting.Character helper) { 547 int n = x.length; 548 for (int i = 2; i <= n; ++i) { 549 siftUp(x, i, helper); 550 } 551 for (int i = n; i >= 2; --i) { 552 helper.swap(x, 0, i - 1); 553 siftDown(x, i - 1, helper); 554 } 555 return x; 556 } 557 558 private static void siftUp(char[] x, 559 int c, // 1-based index 560 Sorting.Character helper) { 561 int p = c >> 1; // 1-based index 562 while (p >= 1) { 563 if (helper.comesBefore(x, p - 1, c - 1)) { 564 helper.swap(x, p - 1, c - 1); 565 } else { 566 break; 567 } 568 c = p; 569 p = c >> 1; 570 } 571 } 572 573 private static void siftDown(char[] x, 574 int n, // 1-based index 575 Sorting.Character helper) { 576 int p = 1; // 1-based index 577 int ca = 2; // 1-based index 578 int cb = 3; // 1-based index 579 while (ca <= n) { 580 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 581 if (helper.comesBefore(x, p - 1, cb - 1)) { 582 helper.swap(x, p - 1, cb - 1); 583 p = cb; 584 } else { 585 break; 586 } 587 } else { 588 if (helper.comesBefore(x, p - 1, ca - 1)) { 589 helper.swap(x, p - 1, ca - 1); 590 p = ca; 591 } else { 592 break; 593 } 594 } 595 ca = p << 1; 596 cb = ca + 1; 597 } 598 } 599 600 /** 601 * Sort the given array of type <code>short[]</code>. The given helper object is 602 * used to determine the desired ordering of the array elements and to swap 603 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 604 * algorithm is used. 605 * 606 * @param x Array to be sorted. 607 * @param helper Helper object. 608 * @return The array that was sorted (<code>x</code>). 609 */ 610 public static short[] sort(short[] x, 611 Sorting.Short helper) { 612 int n = x.length; 613 for (int i = 2; i <= n; ++i) { 614 siftUp(x, i, helper); 615 } 616 for (int i = n; i >= 2; --i) { 617 helper.swap(x, 0, i - 1); 618 siftDown(x, i - 1, helper); 619 } 620 return x; 621 } 622 623 private static void siftUp(short[] x, 624 int c, // 1-based index 625 Sorting.Short helper) { 626 int p = c >> 1; // 1-based index 627 while (p >= 1) { 628 if (helper.comesBefore(x, p - 1, c - 1)) { 629 helper.swap(x, p - 1, c - 1); 630 } else { 631 break; 632 } 633 c = p; 634 p = c >> 1; 635 } 636 } 637 638 private static void siftDown(short[] x, 639 int n, // 1-based index 640 Sorting.Short helper) { 641 int p = 1; // 1-based index 642 int ca = 2; // 1-based index 643 int cb = 3; // 1-based index 644 while (ca <= n) { 645 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 646 if (helper.comesBefore(x, p - 1, cb - 1)) { 647 helper.swap(x, p - 1, cb - 1); 648 p = cb; 649 } else { 650 break; 651 } 652 } else { 653 if (helper.comesBefore(x, p - 1, ca - 1)) { 654 helper.swap(x, p - 1, ca - 1); 655 p = ca; 656 } else { 657 break; 658 } 659 } 660 ca = p << 1; 661 cb = ca + 1; 662 } 663 } 664 665 /** 666 * Sort the given array of type <code>int[]</code>. The given helper object is 667 * used to determine the desired ordering of the array elements and to swap 668 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 669 * algorithm is used. 670 * 671 * @param x Array to be sorted. 672 * @param helper Helper object. 673 * @return The array that was sorted (<code>x</code>). 674 */ 675 public static int[] sort(int[] x, 676 Sorting.Integer helper) { 677 int n = x.length; 678 for (int i = 2; i <= n; ++i) { 679 siftUp(x, i, helper); 680 } 681 for (int i = n; i >= 2; --i) { 682 helper.swap(x, 0, i - 1); 683 siftDown(x, i - 1, helper); 684 } 685 return x; 686 } 687 688 private static void siftUp(int[] x, 689 int c, // 1-based index 690 Sorting.Integer helper) { 691 int p = c >> 1; // 1-based index 692 while (p >= 1) { 693 if (helper.comesBefore(x, p - 1, c - 1)) { 694 helper.swap(x, p - 1, c - 1); 695 } else { 696 break; 697 } 698 c = p; 699 p = c >> 1; 700 } 701 } 702 703 private static void siftDown(int[] x, 704 int n, // 1-based index 705 Sorting.Integer helper) { 706 int p = 1; // 1-based index 707 int ca = 2; // 1-based index 708 int cb = 3; // 1-based index 709 while (ca <= n) { 710 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 711 if (helper.comesBefore(x, p - 1, cb - 1)) { 712 helper.swap(x, p - 1, cb - 1); 713 p = cb; 714 } else { 715 break; 716 } 717 } else { 718 if (helper.comesBefore(x, p - 1, ca - 1)) { 719 helper.swap(x, p - 1, ca - 1); 720 p = ca; 721 } else { 722 break; 723 } 724 } 725 ca = p << 1; 726 cb = ca + 1; 727 } 728 } 729 730 /** 731 * Sort the given array of type <code>long[]</code>. The given helper object is 732 * used to determine the desired ordering of the array elements and to swap 733 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 734 * algorithm is used. 735 * 736 * @param x Array to be sorted. 737 * @param helper Helper object. 738 * @return The array that was sorted (<code>x</code>). 739 */ 740 public static long[] sort(long[] x, 741 Sorting.Long helper) { 742 int n = x.length; 743 for (int i = 2; i <= n; ++i) { 744 siftUp(x, i, helper); 745 } 746 for (int i = n; i >= 2; --i) { 747 helper.swap(x, 0, i - 1); 748 siftDown(x, i - 1, helper); 749 } 750 return x; 751 } 752 753 private static void siftUp(long[] x, 754 int c, // 1-based index 755 Sorting.Long helper) { 756 int p = c >> 1; // 1-based index 757 while (p >= 1) { 758 if (helper.comesBefore(x, p - 1, c - 1)) { 759 helper.swap(x, p - 1, c - 1); 760 } else { 761 break; 762 } 763 c = p; 764 p = c >> 1; 765 } 766 } 767 768 private static void siftDown(long[] x, 769 int n, // 1-based index 770 Sorting.Long helper) { 771 int p = 1; // 1-based index 772 int ca = 2; // 1-based index 773 int cb = 3; // 1-based index 774 while (ca <= n) { 775 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 776 if (helper.comesBefore(x, p - 1, cb - 1)) { 777 helper.swap(x, p - 1, cb - 1); 778 p = cb; 779 } else { 780 break; 781 } 782 } else { 783 if (helper.comesBefore(x, p - 1, ca - 1)) { 784 helper.swap(x, p - 1, ca - 1); 785 p = ca; 786 } else { 787 break; 788 } 789 } 790 ca = p << 1; 791 cb = ca + 1; 792 } 793 } 794 795 /** 796 * Sort the given array of type <code>float[]</code>. The given helper object is 797 * used to determine the desired ordering of the array elements and to swap 798 * the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) heapsort 799 * algorithm is used. 800 * 801 * @param x Array to be sorted. 802 * @param helper Helper object. 803 * @return The array that was sorted (<code>x</code>). 804 */ 805 public static float[] sort(float[] x, 806 Sorting.Float helper) { 807 int n = x.length; 808 for (int i = 2; i <= n; ++i) { 809 siftUp(x, i, helper); 810 } 811 for (int i = n; i >= 2; --i) { 812 helper.swap(x, 0, i - 1); 813 siftDown(x, i - 1, helper); 814 } 815 return x; 816 } 817 818 private static void siftUp(float[] x, 819 int c, // 1-based index 820 Sorting.Float helper) { 821 int p = c >> 1; // 1-based index 822 while (p >= 1) { 823 if (helper.comesBefore(x, p - 1, c - 1)) { 824 helper.swap(x, p - 1, c - 1); 825 } else { 826 break; 827 } 828 c = p; 829 p = c >> 1; 830 } 831 } 832 833 private static void siftDown(float[] x, 834 int n, // 1-based index 835 Sorting.Float helper) { 836 int p = 1; // 1-based index 837 int ca = 2; // 1-based index 838 int cb = 3; // 1-based index 839 while (ca <= n) { 840 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 841 if (helper.comesBefore(x, p - 1, cb - 1)) { 842 helper.swap(x, p - 1, cb - 1); 843 p = cb; 844 } else { 845 break; 846 } 847 } else { 848 if (helper.comesBefore(x, p - 1, ca - 1)) { 849 helper.swap(x, p - 1, ca - 1); 850 p = ca; 851 } else { 852 break; 853 } 854 } 855 ca = p << 1; 856 cb = ca + 1; 857 } 858 } 859 860 /** 861 * Sort the given array of type <code>double[]</code>. The given helper object 862 * is used to determine the desired ordering of the array elements and to 863 * swap the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) 864 * heapsort algorithm is used. 865 * 866 * @param x Array to be sorted. 867 * @param helper Helper object. 868 * @return The array that was sorted (<code>x</code>). 869 */ 870 public static double[] sort(double[] x, 871 Sorting.Double helper) { 872 int n = x.length; 873 for (int i = 2; i <= n; ++i) { 874 siftUp(x, i, helper); 875 } 876 for (int i = n; i >= 2; --i) { 877 helper.swap(x, 0, i - 1); 878 siftDown(x, i - 1, helper); 879 } 880 return x; 881 } 882 883 private static void siftUp(double[] x, 884 int c, // 1-based index 885 Sorting.Double helper) { 886 int p = c >> 1; // 1-based index 887 while (p >= 1) { 888 if (helper.comesBefore(x, p - 1, c - 1)) { 889 helper.swap(x, p - 1, c - 1); 890 } else { 891 break; 892 } 893 c = p; 894 p = c >> 1; 895 } 896 } 897 898 private static void siftDown(double[] x, 899 int n, // 1-based index 900 Sorting.Double helper) { 901 int p = 1; // 1-based index 902 int ca = 2; // 1-based index 903 int cb = 3; // 1-based index 904 while (ca <= n) { 905 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 906 if (helper.comesBefore(x, p - 1, cb - 1)) { 907 helper.swap(x, p - 1, cb - 1); 908 p = cb; 909 } else { 910 break; 911 } 912 } else { 913 if (helper.comesBefore(x, p - 1, ca - 1)) { 914 helper.swap(x, p - 1, ca - 1); 915 p = ca; 916 } else { 917 break; 918 } 919 } 920 ca = p << 1; 921 cb = ca + 1; 922 } 923 } 924 925 /** 926 * Sort the given object array of type <code>T[]</code>. The given helper object 927 * is used to determine the desired ordering of the array elements and to 928 * swap the array elements. An <I>O</I>(<I>n</I> log <I>n</I>) 929 * heapsort algorithm is used. 930 * 931 * @param <T> Data type of the array elements. 932 * @param x Array to be sorted. 933 * @param helper Helper object. 934 * @return The array that was sorted (<code>x</code>). 935 */ 936 public static <T> T[] sort(T[] x, 937 Sorting.Object<T> helper) { 938 int n = x.length; 939 for (int i = 2; i <= n; ++i) { 940 siftUp(x, i, helper); 941 } 942 for (int i = n; i >= 2; --i) { 943 helper.swap(x, 0, i - 1); 944 siftDown(x, i - 1, helper); 945 } 946 return x; 947 } 948 949 private static <T> void siftUp(T[] x, 950 int c, // 1-based index 951 Sorting.Object<T> helper) { 952 int p = c >> 1; // 1-based index 953 while (p >= 1) { 954 if (helper.comesBefore(x, p - 1, c - 1)) { 955 helper.swap(x, p - 1, c - 1); 956 } else { 957 break; 958 } 959 c = p; 960 p = c >> 1; 961 } 962 } 963 964 private static <T> void siftDown(T[] x, 965 int n, // 1-based index 966 Sorting.Object<T> helper) { 967 int p = 1; // 1-based index 968 int ca = 2; // 1-based index 969 int cb = 3; // 1-based index 970 while (ca <= n) { 971 if (cb <= n && helper.comesBefore(x, ca - 1, cb - 1)) { 972 if (helper.comesBefore(x, p - 1, cb - 1)) { 973 helper.swap(x, p - 1, cb - 1); 974 p = cb; 975 } else { 976 break; 977 } 978 } else { 979 if (helper.comesBefore(x, p - 1, ca - 1)) { 980 helper.swap(x, p - 1, ca - 1); 981 p = ca; 982 } else { 983 break; 984 } 985 } 986 ca = p << 1; 987 cb = ca + 1; 988 } 989 } 990 991 // Unit test main program. 992 // /** 993 // * Unit test main program. 994 // * <P> 995 // * Usage: java edu.rit.util.Sorting <I>n</I> <I>seed</I> 996 // * <BR><I>n</I> = Array length 997 // * <BR><I>seed</I> = Random seed 998 // */ 999 // public static void main 1000 // (String[] args) 1001 // { 1002 // if (args.length != 2) usage(); 1003 // int n = java.lang.Integer.parseInt (args[0]); 1004 // long seed = java.lang.Long.parseLong (args[1]); 1005 // byte[] x = new byte [n]; 1006 // Random prng = Random.getInstance (seed); 1007 // for (int i = 0; i < n; ++ i) x[i] = prng.nextByte(); 1008 // for (int i = 0; i < n; ++ i) System.out.printf ("%d ", x[i]); 1009 // System.out.println(); 1010 // Sorting.sort (x, new Sorting.Byte()); 1011 // for (int i = 0; i < n; ++ i) System.out.printf ("%d ", x[i]); 1012 // System.out.println(); 1013 // } 1014 // 1015 // /** 1016 // * Print a usage message and exit. 1017 // */ 1018 // private static void usage() 1019 // { 1020 // System.err.println ("Usage: java edu.rit.util.Sorting <n> <seed>"); 1021 // System.err.println ("<n> = Array length"); 1022 // System.err.println ("<seed> = Random seed"); 1023 // System.exit (1); 1024 // } 1025 }