wood burning stoves 2.0*
The moose likes Java in General and the fly likes need to find quicksort that sorts in descending order ..ARG Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "need to find quicksort that sorts in descending order ..ARG" Watch "need to find quicksort that sorts in descending order ..ARG" New topic
Author

need to find quicksort that sorts in descending order ..ARG

luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
Hey everyone, i have just been going back through some of the code i have written for my current project and realized i used alot of slow algorithms for sorting and started going back to change them, but for a certain segments of code i need to sort a vector of objects, containg double values, in descending order.Seems that i can only find a quicksort algorithm that sorts in ascending order.And by looking at the code i have for that algoirthm it seems like it owuld be easy to change, but it hasnt been.Deadline is coming up here next week and wouldnt mind a hand improving the speed with this algorithm.

Ill post the code i have written..(well changed to suit my needs) for the quicksort, now i just need it in descending order.Any help would be great
***just a note.the utility packet's getMean() method returns a double value



i have tryed swapping a few of the comparison signs and figured that might work..but i keep gettin an array index outa bounds error...so something is messing up.Anyways if anyone has time to take a gander it would be great.thanks
P.S-this is the code for the ascending order....works just perfect
-luc
[ March 21, 2005: Message edited by: luc comeau ]

National Research Council<br />Internet Logic Department
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

There's no reason to write your own sorting routines, They're notoriously hard to get right, first of all, and they obviously add a maintenence burden. Worst of all, unmodified QuickSort has some serious worst-case performance issues.

To sort a Vector, you can simply use the static sort(List) method in java.util.Collections. There's a version that takes a Comparator as a second argument, and so you can control the sort order simply by supplying an appropriate Comparator object. These sort methods perform very well in real-world situations and avoid the worst-case behavior.


[Jess in Action][AskingGoodQuestions]
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hey Ernest,
You make a valid point about not writing my own sorting routine.I am considering your request about using the sort method in that class, but i have a problem, its going to use the compareTo method to compare the obejcts in the list i pass to it...but how is it going to know if my UtilityPacket 1, is greater then UtilityPacket 2....if i have writen that class myself?What exactly does it compare?I need it so that it only compares the means of each UtilityPacket then swaps the entire obejct itself based on the comparison.

If i passed it a list with just the means in it, and it ordered that list of means(double values) that does me no good because now the utilityPackets name and standard deviation are no longer attached.Do you see my problem? Again i could be completly wrong about the compareTo thing becuase i am by no means a java expert.See if you can understand what iv said and try to straighten me out lol.Thanks again
P.S- in the mean time ill look at this "comparator" class, never used it before.
-luc
[ March 21, 2005: Message edited by: luc comeau ]
Stefan Willi
Ranch Hand

Joined: Mar 11, 2005
Posts: 47
Hi!

If you want to sort your object ina natural order, then the compareTo Method will fit to you. You have to implement the interface java.lang.Comperable and code your logic of comparing 2 objects.

If you want to sort your objects about different rules, then the java.lang.Comperator class will be the right for you.

Generally, each method wich compares tho object is returning an int value, which indicates the order. Have a look at API Comparable

stefan

and now, my leisure time is starting...
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hey,ok i remember now about writing your own compareTo method.Im prety sure i can do that easily.But in order to use the java.util.collections sort method for sorting in descending order i have to use the sort(list,comparator) method, and i dont know how to use this comparator class yet.Can any one maybe point to a direction that has some good examples of using this class, or maybe if its not hard think one up for how i would use it.No stress if its too hard dont worry about it.Thanks
-luc
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
heres the compareTo method, works fine.

can i use this somehow with comparator?Bah i just need an example lol
Horatio Westock
Ranch Hand

Joined: Feb 23, 2005
Posts: 221
Hi,

To create a comparator, you simply need to create a class that implements the Comparator interface, that is, implements the method "public int compare(Object o1, Object o2)"

So, since you have a compareTo method for your type, you can basically use that in you implementation:



Now, to give yourself control over the sort order, you just need to add a constructor to TestComparator that allows you to pass in a value indicating the order (this could be a simple boolean, or some enumerated type). In the constructor, store this value somewhere. Then in the compare method, change the sort order based upon the value. In the case of a simple ascending/descending order, you can simply negate the value from compareTo.
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
hi horatio, first off cool name
Second
In the case of a simple ascending/descending order, you can simply negate the value from compareTo.


This is kind of unclear to me.
Say i write a constructor something like...
//have a private variable descending, if its true then the ordering should be //in descending
public TestComparator(Boolean descendingIn){
descending=descendingIn;
}
now say if i construct this class with TestComparator(true),how exactly am i to use that input value of true to make sure the list sorts in descending order?I kindof get the idea that i would say somewhere in my compare method
if(descending)
then..somehow make sure it sorts in descending order...but i duno how to do this.
If you can be a little more clear that would be awesome.Thanks again for your help.
-luc
Horatio Westock
Ranch Hand

Joined: Feb 23, 2005
Posts: 221
How about:

Manish Malik
Greenhorn

Joined: Jan 27, 2001
Posts: 19
Originally posted by luc comeau:
now say if i construct this class with TestComparator(true),how exactly am i to use that input value of true to make sure the list sorts in descending order?I kindof get the idea that i would say somewhere in my compare method
if(descending)
then..somehow make sure it sorts in descending order...but i duno how to do this.


If you check the Java Documentation for

Comparable Interface and the description of compareTo method there, you'll see that the way sort is done depends upon the return value of the compareTo method.

Reverse the return value (positive <-> negative) based upon the boolean flag passed in the constructor, and experiment this way forward.


Manish
Horatio Westock
Ranch Hand

Joined: Feb 23, 2005
Posts: 221
I might just point out, that while this is a nice little discussion about creating comparators, since your type implements comparable (has compareTo), you can just use Collections.reverseOrder() to get a comparator that reverses the natural order. E.g.



It is good to know how to create customer comparators (for more complex sort conditions), but if you just want to get the reverse of the natural order, you can use the above.
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
Excellent discussion, i think i understand whats goin on now, and infact i have tryed this both ways that Horatio has suggested.I wrote my own class...basically like his and that works, also tryed with the reverseOrder() as well and it works too.So i guess this thread has answered my question and in record breaking time!!Much apprieciated folks!Time to see how speedy this is comparative to the sorting method i had in the very first post(even though it didnt exactly dowhat i wanted lol).I noticed this sort method in the Collections class uses a variation of the merge sort...and since i know that the quick sort is a variation or the merge sort...minus the merge, it must be relatively close in the test times.
Anyways thanks everyone!
-Luc
Layne Lund
Ranch Hand

Joined: Dec 06, 2001
Posts: 3061
As EFH points out above, the implementation of Collections.sort() might actually run quicker than your implementation (once you fix it). The difference is that Collections.sort() is fine-tuned so that it is guaranteed to always run in O(n*log(n)). However, in the worst case, a unmodified quick sort can degrade to O(n^2). IIRC, the worst case for quick sort is an already-sorted array, however you should look this up to be sure. Sorting is a well-known topic and there is information all over the Web about it.

I apologize if this is a bit too technical. If you are unfamiliar with Big-Oh notation, I suggest that you do some research, either through Google or a text. In particlar, Big-Oh notation is part of the broader topic of Analysis of Algorithms.

Keep Coding!

Layne


Java API Documentation
The Java Tutorial
luc comeau
Ranch Hand

Joined: Jan 20, 2005
Posts: 97
thanks layne!Yes i am familiar with the Big Oh , but non the less possibly when other people read this thread they may learn something, right?, thats what these forums are for .Thanks.

P.S-i got the hole shabang working and its just as fast as the origianl quicksort i was using(which was way too complicated to post on here for people to try to help me fix).I am doing many other recursive calls and calculation in my program and it still managed to sort 2^18 elements in a little under ten seconds.Although 2^19 i run out of memory lol...its not a big deal though considering i don't think my program will ever have to sort any more then 2^10 elements so all in all it works terrific!
-luc
 
Don't get me started about those stupid light bulbs.
 
subject: need to find quicksort that sorts in descending order ..ARG