• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Jj Roberts
  • Tim Holloway
  • Piet Souris
Bartenders:
  • Himai Minh
  • Carey Brown
  • salvin francis

Comparing values

 
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,
 
Bartender
Posts: 1840
Eclipse IDE Ruby Java
  • 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;
}
}

}
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic