Main Page | Packages | Class Hierarchy | Class List | Directories | File List | Class Members | Related Pages

Sort.java

00001 /*
00002  * OpenMobileIS - a free Java(TM) Framework for mobile applications Java(TM)
00003  * Copyright (C) 2004-2005 Philippe Delrieu
00004  * All rights reserved.
00005  * Contact: openmobileis@e-care.fr
00006  *
00007  * This library is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or any later version.
00011  *
00012  * This library is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with this library; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307
00020  * USA
00021  *
00022  *  Author : Philippe Delrieu
00023  *  
00024  *  Modifications :
00025  *  2004 Creation P.Delrieu
00026  * 
00027  */
00028 
00029 package org.openmobileis.common.util.collection;
00030 
00031 import java.util.Vector;
00032 
00040 public class Sort {
00041 
00042         // no one should instantiate this class
00043 
00044         private Sort() {}
00045 
00056         public synchronized static void shellsort(Vector vec, Orderable op)
00057         {
00058                 if (vec == null || op == null)
00059                         throw new IllegalArgumentException("null argument");
00060 
00061                 int n = vec.size();
00062                 if (n < 2)
00063                         return;
00064 
00065                 // copy out Vector slots to speed things up
00066     int i = 0;
00067                 Object new_vec[] = new Object[n];
00068                 for (i = 0; i < n; i++)
00069                         new_vec[i] = vec.elementAt(i);
00070 
00071     shellsort(new_vec, op);
00072 
00073                 // copy back to Vector
00074 
00075                 for (i = 0; i < n; i++)
00076                         vec.setElementAt(new_vec[i], i);
00077         }
00078 
00079 
00091         public synchronized static void shellsort(Array array, Orderable op)    {
00092                 if (array == null || op == null)
00093                         throw new IllegalArgumentException("null argument");
00094 
00095                 int n = array.size();
00096                 if (n < 2)
00097                         return;
00098 
00099                 // copy out Vector slots to speed things up
00100                 Object new_vec[] = new Object[n];
00101                 System.arraycopy(array.getArrayElements(),0, new_vec, 0, n);
00102 
00103     shellsort(new_vec, op);
00104 
00105                 // copy back to Vector
00106     array.setArrayElements(new_vec);
00107         }
00108 
00109   public static void shellsort(Object[] data, Orderable op)  {
00110                 // sort using Shellsort
00111                 int h = 1;
00112                 int i = 0;
00113                 int n = data.length;
00114 
00115 
00116                 while (h <= n)
00117                         h = h * 3 + 1;
00118                 while (h > 1) {
00119                         h /= 3;
00120                         for (i = h + 1; i <= n; i++) {
00121                                 Object v = data[i - 1];
00122                                 int j = i;
00123                                 while (op.compareTo(data[j - h - 1], v) > 0) {
00124                                         data[j - 1] = data[j - h - 1];
00125                                         j -= h;
00126                                         if (j <= h)
00127                                                 break;
00128                                 }
00129                                 data[j - 1] = v;
00130                         }
00131                 }
00132   }
00133 
00134 }

Generated on Wed Dec 14 21:05:35 2005 for OpenMobileIS by  doxygen 1.4.4