1 /* 2 * This program is free software; you can redistribute it and/or 3 * modify it under the terms of the GNU General Public License as 4 * published by the Free Software Foundation; either version 2 of the 5 * License, or (at your option) any later version. 6 * 7 * This program is distributed in the hope that it will be useful, but 8 * WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOUSE. See the GNU 10 * General Public License for more details. 11 * 12 * You should have recieved a copy of the GNU General Public License 13 * along with this program; if not write to the Free Software 14 * Foundation, inc., 59 Temple Place, Suite 330, Boston MA 02111-1307 15 * USA 16 */ 17 package util; 18 import j3d.shp; 19 20 import java.util.*; 21 /** 22 * Insert the type's description here. 23 * 24 * @author: Yuriy Mikhaylovskiy 25 */ 26 27 public class QSortZ{ QuickSort(Vector v, int lo0, int hi0)28 private void QuickSort(Vector v, int lo0, int hi0){ 29 int lo = lo0; 30 int hi = hi0; 31 float mid; 32 33 if ( hi0 > lo0){ 34 35 /* Arbitrarily establishing partition element as the midpoint of 36 * the array. 37 */ 38 mid = ((shp)v.elementAt(( lo0 + hi0 )/2)).get_Z(); 39 40 // loop through the array until indices cross 41 while( lo <= hi ) { 42 /* find the first element that is greater than or equal to 43 * the partition element starting from the left Index. 44 */ 45 while( ( lo < hi0 ) && ( ((shp)v.elementAt(lo)).get_Z() < mid )) 46 ++lo; 47 48 /* find an element that is smaller than or equal to 49 * the partition element starting from the right Index. 50 */ 51 while( ( hi > lo0 ) && ( ((shp)v.elementAt(hi)).get_Z() > mid )) 52 --hi; 53 54 // if the indexes have not crossed, swap 55 if( lo <= hi ) { 56 swap(v, lo, hi); 57 ++lo; 58 --hi; 59 } 60 } 61 62 /* If the right index has not reached the left side of array 63 * must now sort the left partition. 64 */ 65 if( lo0 < hi ) 66 QuickSort(v, lo0, hi); 67 68 /* If the left index has not reached the right side of array 69 * must now sort the right partition. 70 */ 71 if( lo < hi0 ) QuickSort(v, lo, hi0); 72 } 73 } 74 swap(Vector v, int i, int j)75 private void swap(Vector v, int i, int j){ 76 Object T = v.elementAt(i); 77 v.setElementAt(v.elementAt(j),i); 78 v.setElementAt(T,j); 79 } 80 sort(Vector v)81 public void sort(Vector v){ 82 QuickSort(v, 0, v.size()-1); 83 } 84 85 } 86