Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Comparing values

 
Nick Delauney
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello all,
I have a quicksort algorithm (Wiess) that compares objects. However when it compares an Integer, Double, Float object; It does so in an alphabetical manner so that this order is valid:
112233
1465
18
2
-or for float/doubles-
126.33
13.9
But I would like it to compare values and sort
in this manner:
2
18
1465
112233
-or for float/doubles-
13.9
126.33
So far the algorithm works fine with strings and chars, but I would like it to work with Floats, Doubles, and Integers in the fashion mentioned above.
Thanks for any help,
 
Joel McNary
Bartender
Posts: 1840
Eclipse IDE Java Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you write your quicksort method to accept objects that implement the java.lang.Comparable interface, then you should be OK. Sounds like your method is calling .toString() or something else to do the comparison, but without seeing your code I can't tell for sure.
 
Nick Delauney
Ranch Hand
Posts: 43
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is the algorithm:
Could "compareTo" cause the problem ?
The code:
---------------------------------
/**
* Quicksort algorithm.
* @param a an array of Comparable items.
*/
public static void sort( Comparable [ ] a )
{
sort( a, 0, a.length - 1 );
}

private static final int CUTOFF = 10;

/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/

public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}

/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
private static Comparable median3( Comparable [ ] a, int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, center );
if( a[ right ].compareTo( a[ left ] ) < 0 )
swapReferences( a, left, right );
if( a[ right ].compareTo( a[ center ] ) < 0 )
swapReferences( a, center, right );
// Place pivot at position right - 1
swapReferences( a, center, right - 1 );
return a[ right - 1 ];
}

/**
* Internal sort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void sort( Comparable [ ] a, int left, int right )
{

if( left + CUTOFF <= right )
{
Comparable pivot = median3( a, left, right );
// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ].compareTo( pivot ) < 0 ) { }
while( a[ --j ].compareTo( pivot ) > 0 ) { }
if( i < j )
swapReferences( a, i, j );
else
break;
}
swapReferences( a, i, right - 1 ); // Restore pivot
sort( a, left, i - 1 ); // Sort small elements
sort( a, i + 1, right ); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}

/**
* Internal insertion sort routine for subarrays
* that is used by sort.
* @param a an array of Comparable items.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void insertionSort( Comparable [ ] a, int left, int right )
{
for( int p = left + 1; p <= right; p++ )
{
Comparable tmp = a[ p ];
int j;
for( j = p; j > left && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
a[ j ] = a[ j - 1 ];
a[ j ] = tmp;
}
}

}
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic