SplitSort.java

Go to the documentation of this file.

package sorter;

import java.util.*;


public class SplitSort
{

      00024       // Fields
      00026 
      private List<Integer> greater;
      private List<Integer> smaller;
      private List<Integer[]> sorted;
      private List<Boolean> comparisons;
      private Integer numberOfElements;
      private Integer minimalSize;

      00064       // Constructor
      00066 
      public SplitSort( List<Integer[]> init, Integer min )
      {
            this.sorted = new ArrayList<Integer[]>();
            this.greater = new ArrayList<Integer>();
            this.smaller= new ArrayList<Integer>();
            this.comparisons = new ArrayList<Boolean>();
            this.minimalSize = min;
            this.numberOfElements = 0;
            for (Integer[] array : init)
            {
                  this.sorted.add(array.clone());
                  this.numberOfElements += array.length ;
            }
      }
      
      00097       // Methods
      00099 

      public Boolean notFinished()
      {
            int count = 0;
            for (Integer[] tab : this.sorted)
                  if (tab.length > this.minimalSize)
                        break;
                  else
                        count+=tab.length;
            return (count != this.numberOfElements);
      }
      

      public void iteration()
      {
            this.comparisons.clear();
            this.greater.clear();
            this.smaller.clear();
            for ( Integer[] tab : this.sorted)
                  if (tab.length > this.minimalSize)
                        addComparisons(tab);
      }


      private void addComparisons( Integer[] tab )
      {
            for (int i=0; i<tab.length; i++)
            {
                  this.greater.add(tab[i]);
                  this.smaller.add(tab[0]);
            }
      }



      public void endIteration( List<Boolean> comparisons )
      {
            int i=0;
            this.comparisons = comparisons;
            while (i<this.sorted.size())
                  if ( this.sorted.get(i).length > this.minimalSize)
                        i+=insertion(i);
                  else
                        i+=1;
      }


      private int insertion( int rank )
      {
            // initialisations
            Integer[] tab = this.sorted.get(rank);
            int pivot = tab[0];
            List<Integer> small = new ArrayList<Integer>() ;
            List<Integer> great = new ArrayList<Integer>() ;
            int pivotIndex = this.smaller.indexOf(pivot);
            
            // creation of the arrays to add
            for (int j=0; j<tab.length; j++)
            {
                  int g = this.greater.get(pivotIndex+j);
                  int s = this.smaller.get(pivotIndex+j);
                  if (this.comparisons.get(pivotIndex+j))
                  {
                        if (s!=pivot) small.add(s);
                        if (g!=pivot) great.add(g);
                  }
                  else
                  {
                        if (g!=pivot) small.add(g);
                        if (s!=pivot) great.add(s);
                  }
            }
            Integer[] great_array = great.toArray(new Integer[0]);
            Integer[] array_pivot =  { pivot };
            Integer[] small_array = small.toArray(new Integer[0]);
            
            // removing and insertion of the right arrays
            this.sorted.remove(rank);
            int ins = 1;      // number of arrays inserted (at least the pivot)
            if (great_array.length>0)
            {
                  this.sorted.add(rank,great_array);
                  ins++;
            }
            this.sorted.add(rank,array_pivot);
            if (small_array.length>0)
            {
                  this.sorted.add(rank,small_array);
                  ins++;
            }
            
            // the number of arrays inserted is returned
            return ins;
      }


      public Integer[] getFinalResult(  )
      {
            List<Integer> result = new ArrayList<Integer>();
            for(int i=0; i<this.sorted.size(); i++)
                  for (int j=0; j<this.sorted.get(i).length; j++)
                        result.add(this.sorted.get(i)[j]);
            return result.toArray(new Integer[0]);
      }


      public void display(  )
      {
            for (Integer[] tab : this.sorted)
            {
                  System.out.print(" [ ");
                  for (Integer i : tab)
                  {
                        System.out.print(i);
                        System.out.print(" ");
                  }
                  System.out.print("] ");
            }
      }


  
      00298       // Accessor methods
      00300 

      public List<Integer> getGreater ( )
      { return this.greater; }
      
      
      public List<Integer> getSmaller ( )
      { return this.smaller; }

      
      public List<Integer[]> getSorted()
      { return this.sorted; }

}