Go to the documentation of this file.00001 package sorter;
00002
00003 import java.util.*;
00004
00005
00020 public class SplitSort
00021 {
00022
00023
00024
00025
00026
00034 private List<Integer> greater;
00040 private List<Integer> smaller;
00046 private List<Integer[]> sorted;
00053 private List<Boolean> comparisons;
00057 private Integer numberOfElements;
00061 private Integer minimalSize;
00062
00063
00064
00065
00066
00081 public SplitSort( List<Integer[]> init, Integer min )
00082 {
00083 this.sorted = new ArrayList<Integer[]>();
00084 this.greater = new ArrayList<Integer>();
00085 this.smaller= new ArrayList<Integer>();
00086 this.comparisons = new ArrayList<Boolean>();
00087 this.minimalSize = min;
00088 this.numberOfElements = 0;
00089 for (Integer[] array : init)
00090 {
00091 this.sorted.add(array.clone());
00092 this.numberOfElements += array.length ;
00093 }
00094 }
00095
00096
00097
00098
00099
00100
00111 public Boolean notFinished()
00112 {
00113 int count = 0;
00114 for (Integer[] tab : this.sorted)
00115 if (tab.length > this.minimalSize)
00116 break;
00117 else
00118 count+=tab.length;
00119 return (count != this.numberOfElements);
00120 }
00121
00122
00134 public void iteration()
00135 {
00136 this.comparisons.clear();
00137 this.greater.clear();
00138 this.smaller.clear();
00139 for ( Integer[] tab : this.sorted)
00140 if (tab.length > this.minimalSize)
00141 addComparisons(tab);
00142 }
00143
00144
00154 private void addComparisons( Integer[] tab )
00155 {
00156 for (int i=0; i<tab.length; i++)
00157 {
00158 this.greater.add(tab[i]);
00159 this.smaller.add(tab[0]);
00160 }
00161 }
00162
00163
00164
00176 public void endIteration( List<Boolean> comparisons )
00177 {
00178 int i=0;
00179 this.comparisons = comparisons;
00180 while (i<this.sorted.size())
00181 if ( this.sorted.get(i).length > this.minimalSize)
00182 i+=insertion(i);
00183 else
00184 i+=1;
00185 }
00186
00187
00206 private int insertion( int rank )
00207 {
00208
00209 Integer[] tab = this.sorted.get(rank);
00210 int pivot = tab[0];
00211 List<Integer> small = new ArrayList<Integer>() ;
00212 List<Integer> great = new ArrayList<Integer>() ;
00213 int pivotIndex = this.smaller.indexOf(pivot);
00214
00215
00216 for (int j=0; j<tab.length; j++)
00217 {
00218 int g = this.greater.get(pivotIndex+j);
00219 int s = this.smaller.get(pivotIndex+j);
00220 if (this.comparisons.get(pivotIndex+j))
00221 {
00222 if (s!=pivot) small.add(s);
00223 if (g!=pivot) great.add(g);
00224 }
00225 else
00226 {
00227 if (g!=pivot) small.add(g);
00228 if (s!=pivot) great.add(s);
00229 }
00230 }
00231 Integer[] great_array = great.toArray(new Integer[0]);
00232 Integer[] array_pivot = { pivot };
00233 Integer[] small_array = small.toArray(new Integer[0]);
00234
00235
00236 this.sorted.remove(rank);
00237 int ins = 1;
00238 if (great_array.length>0)
00239 {
00240 this.sorted.add(rank,great_array);
00241 ins++;
00242 }
00243 this.sorted.add(rank,array_pivot);
00244 if (small_array.length>0)
00245 {
00246 this.sorted.add(rank,small_array);
00247 ins++;
00248 }
00249
00250
00251 return ins;
00252 }
00253
00254
00264 public Integer[] getFinalResult( )
00265 {
00266 List<Integer> result = new ArrayList<Integer>();
00267 for(int i=0; i<this.sorted.size(); i++)
00268 for (int j=0; j<this.sorted.get(i).length; j++)
00269 result.add(this.sorted.get(i)[j]);
00270 return result.toArray(new Integer[0]);
00271 }
00272
00273
00281 public void display( )
00282 {
00283 for (Integer[] tab : this.sorted)
00284 {
00285 System.out.print(" [ ");
00286 for (Integer i : tab)
00287 {
00288 System.out.print(i);
00289 System.out.print(" ");
00290 }
00291 System.out.print("] ");
00292 }
00293 }
00294
00295
00296
00297
00298
00299
00300
00301
00306 public List<Integer> getGreater ( )
00307 { return this.greater; }
00308
00309
00314 public List<Integer> getSmaller ( )
00315 { return this.smaller; }
00316
00317
00322 public List<Integer[]> getSorted()
00323 { return this.sorted; }
00324
00325 }