1 /* 2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * - Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * - Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * - Neither the name of Oracle nor the names of its 16 * contributors may be used to endorse or promote products derived 17 * from this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 20 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 21 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 24 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 25 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 26 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 27 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 28 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 29 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 /* 33 * This source code is provided to illustrate the usage of a given feature 34 * or technique and has been deliberately simplified. Additional steps 35 * required for a production-quality application, such as security checks, 36 * input validation and proper error handling, might not be present in 37 * this sample code. 38 */ 39 40 41 42 /** 43 * A quick sort demonstration algorithm 44 * SortAlgorithm.java 45 * 46 * @author James Gosling 47 * @author Kevin A. Smith 48 */ 49 public class QSortAlgorithm extends SortAlgorithm { 50 51 /** 52 * A version of pause() that makes it easier to ensure that we pause 53 * exactly the right number of times. 54 */ pauseTrue(int lo, int hi)55 private boolean pauseTrue(int lo, int hi) throws Exception { 56 super.pause(lo, hi); 57 return true; 58 } 59 60 /** This is a generic version of C.A.R Hoare's Quick Sort 61 * algorithm. This will handle arrays that are already 62 * sorted, and arrays with duplicate keys.<BR> 63 * 64 * If you think of a one dimensional array as going from 65 * the lowest index on the left to the highest index on the right 66 * then the parameters to this function are lowest index or 67 * left and highest index or right. The first time you call 68 * this function it will be with the parameters 0, a.length - 1. 69 * 70 * @param a an integer array 71 * @param lo0 left boundary of array partition 72 * @param hi0 right boundary of array partition 73 */ QuickSort(int a[], int lo0, int hi0)74 void QuickSort(int a[], int lo0, int hi0) throws Exception { 75 int lo = lo0; 76 int hi = hi0; 77 int mid; 78 79 if (hi0 > lo0) { 80 81 /* Arbitrarily establishing partition element as the midpoint of 82 * the array. 83 */ 84 mid = a[(lo0 + hi0) / 2]; 85 86 // loop through the array until indices cross 87 while (lo <= hi) { 88 /* find the first element that is greater than or equal to 89 * the partition element starting from the left Index. 90 */ 91 while ((lo < hi0) && pauseTrue(lo0, hi0) && (a[lo] < mid)) { 92 ++lo; 93 } 94 95 /* find an element that is smaller than or equal to 96 * the partition element starting from the right Index. 97 */ 98 while ((hi > lo0) && pauseTrue(lo0, hi0) && (a[hi] > mid)) { 99 --hi; 100 } 101 102 // if the indexes have not crossed, swap 103 if (lo <= hi) { 104 swap(a, lo, hi); 105 ++lo; 106 --hi; 107 } 108 } 109 110 /* If the right index has not reached the left side of array 111 * must now sort the left partition. 112 */ 113 if (lo0 < hi) { 114 QuickSort(a, lo0, hi); 115 } 116 117 /* If the left index has not reached the right side of array 118 * must now sort the right partition. 119 */ 120 if (lo < hi0) { 121 QuickSort(a, lo, hi0); 122 } 123 124 } 125 } 126 swap(int a[], int i, int j)127 private void swap(int a[], int i, int j) { 128 int T; 129 T = a[i]; 130 a[i] = a[j]; 131 a[j] = T; 132 133 } 134 135 @Override sort(int a[])136 public void sort(int a[]) throws Exception { 137 QuickSort(a, 0, a.length - 1); 138 } 139 } 140