FileDocCategorySizeDatePackage
Sortable.javaAPI DocExample17626Wed Apr 24 12:30:02 BST 2002tuning.sorting

Sortable

public class Sortable extends Object implements Comparable

Fields Summary
static int
SEED
int
order
Constructors Summary
public Sortable(int i)

    order = i;
Methods Summary
public intcompareTo(java.lang.Object o)

return order - ((Sortable) o).order;
public intcompareToSortable(tuning.sorting.Sortable o)

return order - o.order;
public static voidmain(java.lang.String[] args)

    maintest(args);
    if (args.length > 1)
      maintest(args);
public static voidmaintest(java.lang.String[] args)

    int SIZE = Integer.parseInt(args[0]);
    Sortable[] list = new Sortable[SIZE];
    for (int i = SIZE-1; i >= 0; i--)
      list[i] = new Sortable(i);

    long time ;
    Sortable[] listToSort;
    list = randomized(list);
    listToSort = (Sortable[]) list.clone();
    ArrayQuickSorter.SINGLETON.sort(new SortableComparer(), listToSort, 0, listToSort.length);
    quicksort_Sortable2(listToSort, 0, listToSort.length-1);
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");

    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    ArrayQuickSorter.SINGLETON.sort(new SortableComparer(), listToSort, 0, listToSort.length);
    System.out.println("ArrayQuickSorter time using Sortable.method: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println(listToSort[i].order + " here " + i);

    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    ArrayQuickSorter.SINGLETON.sort(new SortableComparer2(), listToSort, 0, listToSort.length);
    System.out.println("ArrayQuickSorter time using Sortable.field: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println(listToSort[i].order + " here " + i);

    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    quicksort_Sortable2(listToSort, 0, listToSort.length-1);
    System.out.println("quicksort time using Sortable.field: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");

    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    quicksort_Sortable1(listToSort, 0, listToSort.length-1);
    System.out.println("quicksort time using Sortable.method: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");
    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    quicksort_Comparable(listToSort, 0, listToSort.length-1);
    System.out.println("quicksort time using Comparable: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");

    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    quicksort_Object(listToSort, 0, listToSort.length-1);
    System.out.println("quicksort time using Object: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");
    listToSort = (Sortable[]) list.clone();
    time = System.currentTimeMillis();
    Arrays.sort(listToSort, 0, listToSort.length);
    System.out.println("quicksort time using Arrays.sort: " + 
      (System.currentTimeMillis()-time));
    for (int i = SIZE-1; i >= 0; i--)
      if(listToSort[i].order != i)
	System.out.println("here");
public static voidquicksort_Comparable(java.lang.Comparable[] arr, int lo, int hi)

    if( lo >= hi ) 
      return;

    int mid = ( lo + hi ) / 2;
    Comparable tmp;
    Comparable middle = arr[ mid ];

    if( arr[ lo ].compareTo(middle) > 0 )
    {
      arr[ mid ] = arr[ lo ];
      arr[ lo ] = middle;
      middle = arr[ mid ];
    }
    
    if( middle.compareTo(arr[ hi ]) > 0)
    {
      arr[ mid ] = arr[ hi ];
      arr[ hi ] = middle;
      middle = arr[ mid ];

      if( arr[ lo ].compareTo(middle) > 0)
      {
        arr[ mid ] = arr[ lo ];
        arr[ lo ] = middle;
        middle = arr[ mid ];
      }
    }

    int left = lo + 1;
    int right = hi - 1;

    if( left >= right ) 
      return;

    for( ;; ) 
    {
      while( arr[ right ].compareTo(middle ) > 0)
      {
        right--;
      }

      while( left < right && arr[ left ].compareTo(middle ) <= 0)
      {
        left++;
      }

      if( left < right )
      {
        tmp = arr[ left ];
        arr[ left ] = arr[ right ];
        arr[ right ] = tmp;
        right--;
      }
      else
      {
        break;
      }
    }

    quicksort_Comparable(arr, lo, left);
    quicksort_Comparable(arr, left + 1, hi);
public static voidquicksort_Object(java.lang.Object[] arr, int lo, int hi)

    if( lo >= hi ) 
      return;

    int mid = ( lo + hi ) / 2;
    Object tmp;
    Object middle = arr[ mid ];

    if( ((Comparable) arr[ lo ]).compareTo(middle) > 0 )
    {
      arr[ mid ] = arr[ lo ];
      arr[ lo ] = middle;
      middle = arr[ mid ];
    }
    
    if( ((Comparable) middle).compareTo(arr[ hi ]) > 0)
    {
      arr[ mid ] = arr[ hi ];
      arr[ hi ] = middle;
      middle = arr[ mid ];

      if( ((Comparable) arr[ lo ]).compareTo(middle) > 0)
      {
        arr[ mid ] = arr[ lo ];
        arr[ lo ] = middle;
        middle = arr[ mid ];
      }
    }

    int left = lo + 1;
    int right = hi - 1;

    if( left >= right ) 
      return;

    for( ;; ) 
    {
      while( ((Comparable) arr[ right ]).compareTo(middle ) > 0)
      {
        right--;
      }

      while( left < right && ((Comparable) arr[ left ]).compareTo(middle ) <= 0)
      {
        left++;
      }

      if( left < right )
      {
        tmp = arr[ left ];
        arr[ left ] = arr[ right ];
        arr[ right ] = tmp;
        right--;
      }
      else
      {
        break;
      }
    }

    quicksort_Object(arr, lo, left);
    quicksort_Object(arr, left + 1, hi);
public static voidquicksort_Sortable1(tuning.sorting.Sortable[] arr, int lo, int hi)

    if( lo >= hi ) 
      return;

    int mid = ( lo + hi ) / 2;
    Sortable tmp;
    Sortable middle = arr[ mid ];

    if( arr[ lo ].compareToSortable(middle) > 0 )
    {
      arr[ mid ] = arr[ lo ];
      arr[ lo ] = middle;
      middle = arr[ mid ];
    }
    
    if( middle.compareToSortable(arr[ hi ]) > 0)
    {
      arr[ mid ] = arr[ hi ];
      arr[ hi ] = middle;
      middle = arr[ mid ];

      if( arr[ lo ].compareToSortable(middle) > 0)
      {
        arr[ mid ] = arr[ lo ];
        arr[ lo ] = middle;
        middle = arr[ mid ];
      }
    }

    int left = lo + 1;
    int right = hi - 1;

    if( left >= right ) 
      return;

    for( ;; ) 
    {
      while( arr[ right ].compareToSortable(middle ) > 0)
      {
        right--;
      }

      while( left < right && arr[ left ].compareToSortable(middle ) <= 0)
      {
        left++;
      }

      if( left < right )
      {
        tmp = arr[ left ];
        arr[ left ] = arr[ right ];
        arr[ right ] = tmp;
        right--;
      }
      else
      {
        break;
      }
    }

    quicksort_Sortable1(arr, lo, left);
    quicksort_Sortable1(arr, left + 1, hi);
public static voidquicksort_Sortable2(tuning.sorting.Sortable[] arr, int lo, int hi)

    if( lo >= hi ) 
      return;

    int mid = ( lo + hi ) / 2;
    Sortable tmp;
    Sortable middle = arr[ mid ];

    if( arr[ lo ].order > middle.order )
    {
      arr[ mid ] = arr[ lo ];
      arr[ lo ] = middle;
      middle = arr[ mid ];
    }
    
    if( middle.order > arr[ hi ].order)
    {
      arr[ mid ] = arr[ hi ];
      arr[ hi ] = middle;
      middle = arr[ mid ];

      if( arr[ lo ].order > middle.order)
      {
        arr[ mid ] = arr[ lo ];
        arr[ lo ] = middle;
        middle = arr[ mid ];
      }
    }

    int left = lo + 1;
    int right = hi - 1;

    if( left >= right ) 
      return;

    for( ;; ) 
    {
      while( arr[ right ].order > middle.order)
      {
        right--;
      }

      while( left < right && arr[ left ].order <= middle.order )
      {
        left++;
      }

      if( left < right )
      {
        tmp = arr[ left ];
        arr[ left ] = arr[ right ];
        arr[ right ] = tmp;
        right--;
      }
      else
      {
        break;
      }
    }

    quicksort_Sortable2(arr, lo, left);
    quicksort_Sortable2(arr, left + 1, hi);
public static tuning.sorting.Sortable[]randomized(tuning.sorting.Sortable[] arr)

    Sortable[] list = new Sortable[arr.length];
    Sortable[] list2 = (Sortable[]) arr.clone();
    Random rand = new Random(SEED);
    int idx;
    for (int i = list.length-1; i >= 0 ; i--)
    {
	idx = (int) ((Math.abs(rand.nextInt()) * (long) i)/Integer.MAX_VALUE);
	list[i] = list2[idx];
	list2[idx] = list2[i];
	list2[i] = null;
    }
    list2 = null;
    rand = null;
    System.gc();
    return list;