/Users/lyon/j4p/src/collections/sortable/QuickSort.java

1    package collections.sortable; 
2     
3    import java.util.Vector; 
4     
5     
6    public abstract class QuickSort { 
7        private QuickSort() { 
8        } 
9     
10       public static void main(String args[]) { 
11           Vector v = new Vector(); 
12           int a[] = {23, 34, 45, 23, 12, 324, 45, 65, 34, 23, 1, 1, 324}; 
13           for (int i = 0; i < a.length; i++) 
14               v.addElement(new Cint(a[i])); 
15           sort(v, new Vector(), 0, v.size(), true); 
16    
17       } 
18    
19       public static void printVec(String s, Vector v) { 
20           System.out.println("-----> Printing Vector:" + s); 
21           for (int i = 0; i < v.size(); i++) { 
22               System.out.println("Vec:" + i + " " + v.elementAt(i)); 
23           } 
24    
25       } 
26    
27       public static void sort(Vector va) { 
28           Vector v = new Vector(); 
29           sort(va, v, 0, va.size(), true); 
30       } 
31    
32    
33       public static void sort(Vector va, Vector vb, int begin, 
34                               int count, boolean ascending) { 
35    
36           if (count <= 1) 
37               return; 
38           quickSort(va, vb, begin, begin + count - 1, ascending); 
39       } 
40    
41    
42       private static void quickSort(Vector va, Vector vb, 
43                                     int left, int right, boolean ascending) { 
44           int i, j; 
45           Comparable2 pivot; 
46    
47           if (va.size() <= 1) 
48               return; 
49    
50           i = left; 
51           j = right; 
52    
53           // choose middle key as pivot 
54           pivot = (Comparable2) 
55                   va.elementAt((left + right) / 2); 
56    
57           do { 
58               if (ascending) { 
59                   while (i < right && pivot.isGreater( 
60                           (Comparable2) va.elementAt(i))) 
61                       i++; 
62    
63                   while (j > left && pivot.isLess( 
64                           (Comparable) va.elementAt(j))) 
65                       j--; 
66               } else { 
67                   while (i < right && pivot.isLess( 
68                           (Comparable) va.elementAt(i))) 
69                       i++; 
70    
71                   while (j > left && pivot.isGreater( 
72                           (Comparable) va.elementAt(j))) 
73                       j--; 
74               } 
75    
76               if (i < j) { 
77                   swap(va, i, j); 
78                   swap(vb, i, j); 
79               } 
80    
81               if (i <= j) { 
82                   i++; 
83                   j--; 
84               } 
85           } while (i <= j); 
86    
87           // printVec(" Left="+left+"to j="+j+ 
88           //  " Right="+i+ "to "+ right, va); 
89    
90    
91           if (left < j) 
92               quickSort(va, vb, left, j, ascending); 
93    
94           if (i < right) 
95               quickSort(va, vb, i, right, ascending); 
96       } 
97    
98       public static void swap(Vector v, int i, int j) { 
99           if (v == null) return; 
100          if ((v.size() < i) || (v.size() < j)) return; 
101          Object tmp = v.elementAt(i); 
102          v.setElementAt(v.elementAt(j), i); 
103          v.setElementAt(tmp, j); 
104      } 
105   
106   
107  } 
108