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